P4345 [SHOI2015]超能粒子炮·改

题意:求$\sum_{i=1}^{k}C(n,i)\%(P=2333)$

肯定要先拆开,不然怎么做呢(大雾)

把$C(n,i)$用$lucas$分解一下

于是原式$=\sum_{i=1}^{k}C(n/P,k/P)*C(n\%P,k\%P)\%P$

发现介个$k/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-1)*\sum_{i=0}^{P-1}C(n\%P,i)$

$+C(n/P,k/P)*\sum_{i=0}^{k\%P}C(n\%P,i)$(最后一块不一定是整块,单独取出)

发现前面都有个$\sum_{i=0}^{P-1}C(n\%P,i)$,把它提出来

$=\sum_{j=0}^{k/P-1}C(n/P,j)*\sum_{i=0}^{P-1}C(n\%P,i)+C(n/P,k/P)*\sum_{i=0}^{k\%P}C(n\%P,i)$

根据$f$数组的定义再套进去

$=f[n/P][k/P-1]*f[n\%P][P-1]+C(n/P,k/P)*f[k\%P][n\%P]$

先预处理下标$<P$的$f$数组和组合数$C$,再递归一下,$C(n/P,k/P)$用$Lucas$定理搞

end.

 #include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int P=;
int t;ll n,k,c[P+][P+],f[P+][P+];
ll lucas(ll a,ll b){
if(a<b) return ;
if(a==b) return ;
return b?lucas(a/P,b/P)*c[a%P][b%P]%P:;
}
ll F(ll a,ll b){
if(b<) return ;
if(!a||!b) return ;
if(a<P&&b<P) return f[a][b];
ll r1=f[a%P][P-]*F(a/P,b/P-)%P;
ll r2=lucas(a/P,b/P)*f[a%P][b%P]%P;
return (r1+r2)%P;
}
int main(){
for(int i=;i<=P;++i){
c[i][]=c[i][i]=;
for(int j=;j<i;++j)
c[i][j]=(c[i-][j-]+c[i-][j])%P;
}
for(int i=;i<=P;++i){
f[i][]=;
for(int j=;j<=P;++j)//注意f[P][P]以内的都要处理到
f[i][j]=(f[i][j-]+c[i][j])%P;
}
scanf("%d",&t);
while(t--){
scanf("%lld%lld",&n,&k);
printf("%lld\n",F(n,k));
}return ;
}
04-27 04:51