P4345 [SHOI2015] 超能粒子炮·改 题解
Super_Cube
·
·
题解
Solution
设 p=2333，题意为 f(n,k)=\displaystyle\sum_{i=0}^k\binom{n}{i}\bmod p。
由于 p 为质数，有卢卡斯定理：\displaystyle\sum_{i=0}^k\binom{\lfloor\frac{n}{p}\rfloor}{\lfloor\frac{i}{p}\rfloor}\binom{n\bmod p}{i\bmod p}\bmod p。
枚举 $\left\lfloor\dfrac{i}{p}\right\rfloor$：$\left(\displaystyle\sum_{i=0}^{\lfloor\frac{k}{p}\rfloor-1}\binom{\lfloor\frac{n}{p}\rfloor}{i}\sum_{j=0}^{p-1}\binom{n\bmod p}{j}+\binom{\lfloor\frac{n}{p}\rfloor}{\lfloor\frac{k}{p}\rfloor}\sum_{i=0}^{k\bmod p}\binom{n\bmod p}{i}\right)\bmod p$。
观察出三大坨和式都符合 $f$ 的形式，此时把 $f$ 套进去。
即 $\left(f\left(\left\lfloor\dfrac{n}{p}\right\rfloor,\left\lfloor\dfrac{k}{p}\right\rfloor-1\right)f(n\bmod p,p-1)+\displaystyle\binom{\lfloor\frac{n}{p}\rfloor}{\lfloor\frac{k}{p}\rfloor}f(n\bmod p,k\bmod p)\right)\bmod p$。
预处理出 $\forall i,j\in[0,p)$ 的 $f(i,j)$ 与 $\displaystyle\binom{i}{j}$，只需递归计算 $f\left(\left\lfloor\dfrac{n}{p}\right\rfloor,\left\lfloor\dfrac{k}{p}\right\rfloor-1\right)$ 与 $\displaystyle\binom{\lfloor\frac{n}{p}\rfloor}{\lfloor\frac{k}{p}\rfloor}$，其余可直接调用预处理得到的结果。
# Code
```cpp
#include<stdio.h>
typedef long long ll;
const int mod=2333;
int c[mod][mod];
int C(ll n,ll m){
if(n<mod&&m<mod)return c[n][m];
return 1ll*C(n/mod,m/mod)*c[n%mod][m%mod]%mod;
}
int s[mod][mod];
int calc(ll n,ll m){
if(m<0)return 0;
if(n<mod&&m<mod)return s[n][m];
return (1ll*s[n%mod][mod-1]*calc(n/mod,m/mod-1)+1ll*C(n/mod,m/mod)*s[n%mod][m%mod])%mod;
}
int T;
ll n,m;
int main(){
for(int i=0;i<mod;++i){
c[i][0]=c[i][i]=1;
for(int j=1;j<i;++j)
if((c[i][j]=c[i-1][j]+c[i-1][j-1])>=mod)c[i][j]-=mod;
}
for(int i=0;i<mod;++i){
s[i][0]=1;
for(int j=1;j<mod;++j)
if((s[i][j]=s[i][j-1]+c[i][j])>=mod)s[i][j]-=mod;
}
scanf("%d",&T);
while(T--)
scanf("%lld%lld",&n,&m),
printf("%d\n",calc(n,m));
return 0;
}
```