P4345 [SHOI2015]超能粒子炮·改
题意
求\(\sum_{i=0}^k\binom{n}{i}\)，\(T\)组数据
范围
\(T\le 10^5,n,j\le 10^{18}\)
设\(f(n,k)=\sum_{i=0}^k\binom{n}{i}\)
\[\begin{aligned}
&f(n,k)\\
=&\sum_{i=0}^k\binom{n/p}{i/p}\binom{n\%p}{i\%p}\\
=&\sum_{j=0}^{k/p-1}\binom{n/p}{j}\sum_{i=0}^{p-1}\binom{n\%p}{i}+\binom{n/p}{k/p}\sum_{i=0}^{k\%p}\binom{n\%p}{i}\\
=&f(n/p,k/p-1)f(n\%p,p-1)+\binom{n/p}{k/p}f(n\%p,k\%p)
\end{aligned}
\]
&f(n,k)\\
=&\sum_{i=0}^k\binom{n/p}{i/p}\binom{n\%p}{i\%p}\\
=&\sum_{j=0}^{k/p-1}\binom{n/p}{j}\sum_{i=0}^{p-1}\binom{n\%p}{i}+\binom{n/p}{k/p}\sum_{i=0}^{k\%p}\binom{n\%p}{i}\\
=&f(n/p,k/p-1)f(n\%p,p-1)+\binom{n/p}{k/p}f(n\%p,k\%p)
\end{aligned}
\]
然后就是注意边界边界边界...wa了好久...
Code:
// luogu-judger-enable-o2
#include <cstdio>
#define ll long long
const int mod=2333;
int C[mod+10][mod+10],f[mod+10][mod+10],T;
ll n,k;
void init()
{
f[0][0]=C[0][0]=1;
for(int i=1;i<mod;i++)
{
f[i][0]=C[i][0]=1;
for(int j=1;j<=i;j++)
{
C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
f[i][j]=(f[i][j-1]+C[i][j])%mod;
}
}
}
int getC(ll m,ll n)
{
if(m<n) return 0;
if(m<mod) return C[m][n];
return getC(m/mod,n/mod)*getC(m%mod,n%mod)%mod;
}
int min(int x,int y){return x<y?x:y;}
int getF(ll n,ll k)
{
if(k<0) return 0;
if(!n) return 1;//f[0][k]...
if(!k) return 1;//也许是n>=mod?的特判？
if(n<mod) return f[n][min(n,k)];
return (getF(n/mod,k/mod-1)*getF(n%mod,mod-1)%mod
+getC(n/mod,k/mod)*getF(n%mod,k%mod)%mod)%mod;
}
int main()
{
init();
scanf("%d",&T);
while(T--)
{
scanf("%lld%lld",&n,&k);
printf("%d\n",getF(n,k));
}
return 0;
}
2019.1.20