题解 P4345 【[SHOI2015]超能粒子炮·改】

就是运用$Lucas$推一个柿子 首先是前置芝士$Lucas$定理 $$C_{n}^{m}\%p=C_{n/p}^{m/p}*C_{n\%p}^{m\%p}\%p$$ 至于证明 ~~我建议去问一下Lucas本人~~ 至于这道题，我们要求的是这个柿子 $$\sum_{i=0}^kC_{n}^i\%p$$ 于是我们设$f(n,k)=\sum_{i=0}^kC_{n}^i$ 我们就可以化柿子啦 $$f(n,k)=\sum_{i=0}^kC_{n}^i$$ $$\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }=\sum_{i=0}^kC_{n/p}^{i/p}*C_{n\%p}^{i\%p}$$ 这个东西一看就很熟悉，$n/p$啊，显然跟整除分块差不多啊 $$=C_{n/p}^0\sum_{i=0}^{p-1}C_{n\%p}^i+C_{n/p}^1\sum_{i=0}^{p-1}C_{n\%p}^i+...+C_{n/p}^{k/p}\sum_{i=0}^{k\%p}C_{n\%p}^i$$ 前面有$0$到$k/p-1$这些个整块，于是我们可以将$\sum_{i=0}^{p-1}C_{n\%p}^i$提出来 变成 $$\sum_{i=0}^{p-1}C_{n\%p}^i*(C_{n/p}^0+C_{n/p}^1+...C_{n/p}^{k/p-1})$$ 那这个东西岂不是可以写成 $$f(n\%p,p-1)*f(n/p,k/p-1)$$ 在加上那个不完整的块 $\sum_{i=0}^{k\%p}C_{n\%p}^i$可以写成$f(n\%p,k\%p)$ 于是就有 $$f(n,k)=f(n\%p,p-1)*f(n/p,k/p-1)+C_{n/p}^{k/p}*f(n\%p,k\%p)$$ 由于$n\%p$还有$k\%p$都小于$2333$，所以$f(n\%p,p-1)$还有$f(n\%p,k\%p)$可以直接预处理好可以直接求出来 至于那个$C_{n/p}^{k/p}$就直接上$Lucas$好了 时间复杂度$O(p^2+Tlog_{2333}^2n)$ 代码 非常sb的把$C_0^0$当成$0$WA了好几发 ```cpp #include<iostream> #include<cstring> #include<cstdio> #define re register #define LL long long #define maxn 2335 const int P=2333; LL c[maxn+2][maxn+2]; LL f[maxn+2][maxn+2]; inline LL Lucas(LL n,LL m) { if(!m) return 1; if(n==m) return 1; if(n<m) return 0; return c[n%P][m%P]*Lucas(n/P,m/P)%P; } inline LL F(LL n,LL k) { if(k<0) return 0; if(!n) return 1; if(!k) return 1; if(n<P&&k<P) return f[n][k]; return (F(n/P,k/P-1)*f[n%P][P-1]%P+Lucas(n/P,k/P)*f[n%P][k%P]%P)%P; } int main() { int T; scanf("%d",&T); c[0][0]=1; for(re int i=1;i<=maxn;i++) c[i][i]=c[i][0]=1; for(re int i=1;i<=maxn;i++) for(re int j=1;j<i;j++) c[i][j]=(c[i-1][j]+c[i-1][j-1])%P; f[0][0]=1; for(re int i=1;i<=maxn;i++) f[i][0]=1; for(re int i=0;i<=maxn;i++) for(re int j=1;j<=maxn;j++) f[i][j]=(c[i][j]+f[i][j-1])%P; LL n,k; while(T--) { scanf("%lld%lld",&n,&k); printf("%lld\n",F(n,k)); } return 0; } ```