BZOJ4591: [Shoi2015]超能粒子炮·改

超能粒子炮·改"/>

BZOJ4591: [Shoi2015]超能粒子炮·改

BZOJ4591

根据 Lucas $Lucas$定理推出

ans=∑i=02332Cin mod 2333∗∑j=0k/2333−1Cjn/2333+Ck/2333n/2333∗∑i=0k mod 2333Cin mod 2333 $$ans=\sum_{i=0}^{2332}C_{n \space mod\space 2333}^i*\sum_{j=0}^{k/2333-1}C_{n/2333}^j+C_{n/2333}^{k/2333}*\sum_{i=0}^{k\space mod \space 2333}C_{n \space mod \space 2333}^i$$

懒得推了。。就贴别人的吧。
业界良心啊 QAQ $QAQ$.html

【代码】

#include <cstdio>
#include <iostream>
#include <algorithm>
#define N 2335
#define INF 0x7fffffff
#define mod 2333
using namespace std;
typedef long long ll;ll read()
{ll x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}int T;
ll n,k;
int C[N][N],sum[N][N];int Lucas(ll x,ll y)
{if(x<y||y<0) return 0;if(x<mod&&y<mod) return C[x][y];return Lucas(x/mod,y/mod)*C[x%mod][y%mod]%mod;
}int Cal(ll x,ll y)
{if(y<0) return 0;return (Cal(x/mod,y/mod-1)*sum[x%mod][mod-1]%mod+Lucas(x/mod,y/mod)*sum[x%mod][y%mod]%mod)%mod;
}int main()
{T=read();for(int i=0;i<mod;i++){sum[i][0]=C[i][0]=C[i][i]=1;for(int j=1;j<i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;for(int j=1;j<mod;j++) sum[i][j]=(sum[i][j-1]+C[i][j])%mod;}while(T--){n=read(),k=read();printf("%d\n",Cal(n,k));}return 0;
}