【BZOJ4591】[SHOI2015]超能粒子炮·改 （卢卡斯定理）
题面
题解
感天动地！终于不是拓展卢卡斯了！我看到了一个模数，它是质数！！！
看着这个东西就感觉可以递归处理。
令\(f(n,k)\)表示答案。
\[\begin{aligned}
f(n,k)&=\sum_{i=0}^k {n\choose i}\\
&=\sum_{i=0}^k {n/p\choose i/p}*{n\%p\choose i\%p}\\
&=\sum_{x=0}^{p-1}{n\%p\choose x}*\sum_{i=0}^k[i\%p=x]{n/p\choose i/p}\\
&=\sum_{x=0}^{p-1}{n\%p\choose x}*\sum_{i=0}^{(k-x)/p}{n/p\choose i}\\
&=\sum_{x=0}^{p-1}{n\%p\choose x}*f(n/p,(k-x)/p)
\end{aligned}\]
f(n,k)&=\sum_{i=0}^k {n\choose i}\\
&=\sum_{i=0}^k {n/p\choose i/p}*{n\%p\choose i\%p}\\
&=\sum_{x=0}^{p-1}{n\%p\choose x}*\sum_{i=0}^k[i\%p=x]{n/p\choose i/p}\\
&=\sum_{x=0}^{p-1}{n\%p\choose x}*\sum_{i=0}^{(k-x)/p}{n/p\choose i}\\
&=\sum_{x=0}^{p-1}{n\%p\choose x}*f(n/p,(k-x)/p)
\end{aligned}\]
前面那个东西可以提前预处理好前缀和，而后面那个东西最多递归两次。而递归层数也就最多\(6\)层。所以单次复杂度\(O(2^6)\)。卡卡常就洛谷rk1了。。。
#include<iostream>
#include<cstdio>
using namespace std;
#define ll long long
#define MOD 2333
#define MAX 2350
inline ll read()
{
ll x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
int C[MAX][MAX];
int f(ll n,ll k)
{
if(n<MOD)return C[n][min(n,k)];
if(!k)return 1;
int ret=0,x=k%MOD,y=n%MOD;
ret=C[y][min(y,x)]*f(n/MOD,k/MOD);
if(k-x)ret=(ret+(C[y][y]-C[y][min(y,x)]+MOD)*f(n/MOD,(k-x-1)/MOD))%MOD;
return ret;
}
ll n,k;
int main()
{
for(int i=0;i<MAX;++i)C[i][0]=1;
for(int i=1;i<MAX;++i)
for(int j=1;j<=i;++j)
C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;
for(int i=0;i<MAX;++i)
for(int j=1;j<=i;++j)
C[i][j]=(C[i][j]+C[i][j-1])%MOD;
int T=read();
while(T--)
{
n=read();k=read();
printf("%d\n",f(n,k));
}
return 0;
}