题意
给 \(n\) 个 1 和 \(m\) 个 0, 定义一个 01 串的权值为它所有前缀和的最大值 (包括 0), 求可以组成的所有不同串的权值和, 答案对 998244853 取模
思路
由于数据较小, 本题有个 \(O(n^2)\) 比较复杂的 DP 做法, 自行百度...
实际上本题用数学规律可以 \(O(n)\) 做
设 \(f_i\) 表示权值为 \(i\) 的 01 串数量, 直接求不容易, 再设 \(g_i\) 为权值至少为 \(i\) 的 01 串数量, 那么 \(f_i=g_i-g_{i+1}\)
利用求卡特兰数列的一种方法: 将 01 串看做从坐标系 \((0,0)\) 到 \((m,n)\) 的一条路径, 即纵轴为 1, 横轴为 0
此时 \(g_i\) 表示直线 \(y=x+i\), 求经过它的路径; 类比卡特兰数列, 我们将 \((0,0)\) 做个对称点变成 \((-i,i)\), 从 \((-i,i)\) 到 \((m,n)\) 的所有路径均为经过 \(y=x+i\) 的路径, 即 \(g_i=C(n+m,n-i)\)
预处理个组合数即可求出所有的 \(g\), 从而求出答案
然后写出来样例都过不了
问题出在上面的做对称点, 为什么要做对称点? 因为做了对称点后可以保证每条路径都过直线 \(y=x+i\), 但如果 \((0,0)\) 到 \((n,m)\) 本来就必过 \(y=x+i\) 就不能做对称点了
- Code
- #include<bits/stdc++.h>
- #define N 4005
- #define Min(x,y) ((x)<(y)?(x):(y))
- #define Max(x,y) ((x)>(y)?(x):(y))
- using namespace std;
- typedef long long ll;
- const ll mod = 998244853;
- int n,m;
- ll inv[N],jc[N];
- template <class T>
- void read(T &x)
- {
- char c; int sign=1;
- while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;
- while((c=getchar())>='0'&&c<='9') x=(x<<1)+(x<<3)+c-48; x*=sign;
- }
- ll quickpow(ll a,ll b)
- {
- ll ret=1;
- while(b)
- {
- if(b&1) ret=ret*a%mod;
- a=a*a%mod;
- b>>=1;
- }
- return ret;
- }
- void init(int maxn)
- {
- jc[0]=1; for(int i=1;i<=maxn;++i) jc[i]=jc[i-1]*i%mod;
- inv[maxn]=quickpow(jc[maxn],mod-2);
- for(int i=maxn-1;i>=0;--i) inv[i]=inv[i+1]*(i+1)%mod;
- }
- ll C(int n,int m) { return n>=m ? jc[n]*inv[m]%mod*inv[n-m]%mod : 0; }
- ll g(int i) { return (m>n-i) ? C(n+m,n-i) : C(n+m,n); }
- int main()
- {
- read(n);read(m);
- init(N-1);
- ll ans=0;
- for(int i=0;i<=n;++i) ans+=(g(i)-g(i+1))%mod*i%mod;
- cout<<(ans%mod+mod)%mod<<endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3275620.html