[luoguP4345] [SHOI2015]超能粒子炮·改 {lucas}

超能粒子炮·改 {lucas}"/>

[luoguP4345] [SHOI2015]超能粒子炮·改 {lucas}

题目

解题思路

我们求的是 ∑ i = 0 k C n i % p \sum_{i=0}^kC_{n}^i\%p i=0∑k​Cni​%p
我们可以设 f [ n ] [ k ] = ∑ i = 0 k C n i % p f[n][k]=\sum_{i=0}^kC_{n}^i\%p f[n][k]=i=0∑k​Cni​%p
然后用 L u c a s Lucas Lucas拆一下式子， f ( n , k ) = ∑ i = 0 k C n / p i / p ∗ C n % p i % p f(n,k)=\sum_{i=0}^kC_{n/p}^{i/p}*C_{n\%p}^{i\%p} f(n,k)=i=0∑k​Cn/pi/p​∗Cn%pi%p​
= C n / p 0 ∑ i = 0 p − 1 C n % p i + C n / p 1 ∑ i = 0 p − 1 C n % p i + . . . + C n / p k / p ∑ i = 0 k % p C n % p i =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 =Cn/p0​i=0∑p−1​Cn%pi​+Cn/p1​i=0∑p−1​Cn%pi​+...+Cn/pk/p​i=0∑k%p​Cn%pi​

最后可以得到
f ( n , k ) = f ( n % p , p − 1 ) ∗ f ( n / p , k / p − 1 ) + C n / p k / p ∗ 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) f(n,k)=f(n%p,p−1)∗f(n/p,k/p−1)+Cn/pk/p​∗f(n%p,k%p)

代码

#include<cstdio> 
#define ll long long
#define rep(i,x,y) for(register ll i=x;i<=y;i++)
using namespace std; 
const ll maxn=2335,p=2333; 
ll c[maxn+2][maxn+2],f[maxn+2][maxn+2],T; 
inline ll lucas(ll n,ll m){if (m==0||n==m) return 1; if (n<m) return 0; return lucas(n/p,m/p)*c[n%p][m%p]%p; 
}
inline ll F(ll n,ll k){if (!n||!k) return 1; if (k<0) return 0; 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; 
}
int main(){scanf("%lld",&T);c[0][0]=f[0][0]=1;  ll n,k; rep(i,1,maxn) c[i][i]=c[i][0]=1; rep(i,1,maxn) f[i][0]=1;rep(i,1,maxn) rep(j,1,i-1) c[i][j]=(c[i-1][j]+c[i-1][j-1])%p; rep(i,0,maxn) rep(j,1,maxn) f[i][j]=(c[i][j]+f[i][j-1])%p;while (T--){scanf("%lld%lld",&n,&k); printf("%lld\n",F(n,k)); }
}