首页 > itarticle > 【bzoj4591】 Solution Code

【bzoj4591】 Solution Code

admin 12月 02, 2020 0

　　传送门

Solution

　　记$a=lfloorfrac n prfloor$，$b=n%p$。我们尝试使用Lucas定理展开这些组合数，寻找公共部分。以下除法都作整数下取整除法：

$$
begin{aligned}
f(n,k)&=sum_{i=0}^kC_n^imod p\
&=sum_{i=0}^{ap-1}C_{n/p}^{i/p}_C_{n%p}^{i%p}+sum_{i=ap}^{n}C_{n/p}^{i/p}_C_{n%p}^{i%p}\
&=(sum_{i=0}^{a-1}C_{n/p}^i_sum_{j=0}^{p-1}C_{n%p}^j)+C_{n/p}^{a}_sum_{i=0}^bC_{n%p}^i\
&=f(n/p,a-1)*f(n%p,p-1)+C_{n/p}^{k/p}f(n%p,k%p)
end{aligned}
$$

　　由于模数较小，我们只需要预处理$f(0…p-1,0…p-1)$的值就可以直接计算了。

　　注意判断k<0的情况，此时$f$为0。

Code


using namespace std;
typedef long long ll;
const int MOD=2333,N=2351;
int c[N][N],f[N][N];
inline int (int x,int y){return (x+y)%MOD;}
inline int mul(int x,int y){return 1LL*x*y%MOD;}
inline int C(ll n,ll m){
　　if(n<m) return 0;
　　if(n<MOD&&m<MOD) return c[n][m];
　　return mul(C(n/MOD,m/MOD),C(n%MOD,m%MOD));
}
int solve(ll n,ll k){
　　if(k<0) return 0;
　　if(n<N&&k<N) return f[n][k];
　　return plus(mul(solve(n/MOD,k/MOD-1),f[n%MOD][MOD-1]),mul(C(n/MOD,k/MOD),f[n%MOD][k%MOD]));
}
void init(){
　　c[0][0]=1;
　　for(int i=1;i<N;i++){
　　　　c[i][0]=1;
　　　　for(int j=1;j<N;j++) c[i][j]=plus(c[i-1][j],c[i-1][j-1]);
　　}
　　for(int i=0;i<N;i++){
　　　　f[i][0]=1;
　　　　for(int j=1;j<N;j++) f[i][j]=plus(f[i][j-1],c[i][j]);
　　}
}
int main(){
　　init();       
　　ll T,n,k;
　　scanf("%lld",&T);
　　while(T--){
　　　　scanf("%lld%lld",&n,&k);
　　　　printf("%lldn",solve(n,k));
　　}
　　return 0;
}