题解 P5388 【[Cnoi2019]最终幻想】
cosmicAC
2019-11-01 08:03:46
这题一看就是要求$F(n,k)=\sum_{i=0}^{n}\binom{k}{i}$。然而怎么只有21分？原来n最大可以到mod-1。
于是考虑经典的分块打表。记录一部分的$F(n,k)$，根据洛谷的代码上限50KB，可以计算得到最多能记录10000个数不到。所以我们可以每隔1e7个数记录一个$F(n,k)$。（**打表程序需要求$1\ldots mod-1$的逆元，并且复杂度是$O(100\times mod)$，所以需要很长的时间与大概4G的空间。**）
然后问题就变成了：给定$F(n,k)$，求$F(n+\Delta n,k+\Delta k)$。这个问题可以拆成两个部分，就是从$F(n,k)$求$F(n,k+1)$和$F(n+1,k)$。
从$F(n,k)$求$F(n+1,k)$很简单，就是加上一个$\binom{k}{n+1}$。然后考虑到$\binom{k+1}{n}=\binom{k}{n}+\binom{k}{n-1}$，有
$$F(n,k+1)=\sum_{i=0}^{n}\binom{k+1}{i}$$
$$=\sum_{i=0}^{n}\binom{k}{i}+\binom{k}{i-1}$$
$$=\sum_{i=0}^{n}\binom{k}{i}+\sum_{i=0}^{n-1}\binom{k}{i}$$
$$=2F(n,k)-\binom{k}{n}$$
所以问题被转化为了求一行组合数和一列组合数。先再次打表记录$n!$，暴力求出一个组合数。然后考虑从$\binom{n}{k}$变成$\binom{n}{k+1}$和$\binom{n+1}{k}$，都只要乘一个数再除以一个数，就只需要求2e7个数的逆元，直接离线线性求逆即可。
代码如下：
```cpp
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int siz=10507835;
const ll mod=998244353;
//省略打表数组
int n,k,inv1[siz+10],inv2[siz+10];
ll po(ll a,ll b){ll r=1;for(;b;b/=2,a=a*a%mod)if(b&1)r=r*a%mod;return r;}
ll fac(int x){
ll r=fc[x/siz];
for(int i=x/siz*siz+1;i<=x;i++)(r*=i)%=mod;
return r;
}
ll C(int x,int y){return fac(x)*po(fac(y),mod-2)%mod*po(fac(x-y),mod-2)%mod;}
int main(){
scanf("%d%d",&n,&k);
if(n>=k)printf("%lld\n",po(2,k)),exit(0);
int kk=k/siz*siz,nn=n/siz*siz;
inv1[0]=inv2[0]=1;
for(int i=1;i<=k-kk;i++)inv1[i]=1ll*inv1[i-1]*(i+kk-nn)%mod;
ll now=po(inv1[k-kk],mod-2);if(k>kk)inv1[k-kk]=now*inv1[k-kk-1]%mod;
for(int i=k-kk-1;i>0;i--)
(now*=i+1+kk-nn)%=mod,inv1[i]=now*inv1[i-1]%mod;
for(int i=1;i<=n-nn;i++)inv2[i]=1ll*inv2[i-1]*(i+nn)%mod;
now=po(inv2[n-nn],mod-2);if(n>nn)inv2[n-nn]=now*inv2[n-nn-1]%mod;
for(int i=n-nn-1;i>0;i--)
(now*=i+1+nn)%=mod,inv2[i]=now*inv2[i-1]%mod;
ll res=db[k/siz][n/siz];now=C(kk,nn);
for(int t=kk;t<k;t++){
res=(2*res-now)%mod;
(now*=1ll*(t+1)*inv1[t-kk+1]%mod)%=mod;
}
for(int t=nn;t<n;t++){
(now*=1ll*inv2[t-nn+1]*(k-t)%mod)%=mod;
(res+=now)%=mod;
}
printf("%lld\n",(res+mod)%mod);
return 0;
}
```