超能粒子炮·改 {lucas}"/>
[luoguP4345] [SHOI2015]超能粒子炮·改 {lucas}
题目
解题思路
我们求的是 ∑ i = 0 k C n i % p \sum_{i=0}^kC_{n}^i\%p i=0∑kCni%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∑kCni%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∑kCn/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/p0i=0∑p−1Cn%pi+Cn/p1i=0∑p−1Cn%pi+...+Cn/pk/pi=0∑k%pCn%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)); }
}
更多推荐
[luoguP4345] [SHOI2015]超能粒子炮·改 {lucas}
发布评论