bzoj 4591: [Shoi2015]超能粒子炮·改 Lucas定理+组合数学

组合数学"/>

bzoj 4591: [Shoi2015]超能粒子炮·改 Lucas定理+组合数学

题意

曾经发明了脑洞治疗仪&超能粒子炮的发明家SHTSC又公开了他的新发明：超能粒子炮·改–一种可以发射威力更加强大的粒子流的神秘装置。超能粒子炮·改相比超能粒子炮，在威力上有了本质的提升。它有三个参数n，k。它会向编号为0到k的位置发射威力为C(n,k) mod 2333的粒子流。现在SHTSC给出了他的超能粒子炮·改的参数，让你求其发射的粒子流的威力之和模2333。
k<=n<=10^18，t<=10^5

分析

题目就是要求 (∑ki=0Cin)mod2333 $(\sum_{i=0}^kC_n^i)\bmod 2333$。由于模数很小不难想到Lucas定理 Cmnmodp=Cm/pn/p∗Cmmodpnmodp $C_n^m\bmod p=C_{n/p}^{m/p}*C_{n\bmod p}^{m\bmod p}$。
按照i/p来分类，要求的式子就变成了

∑i=0kCin=∑i=0kCi/pn/p∗Cimodpnmodp=∑i=0k/p−1Cin/p∗∑j=0p−1Cjnmodp+Ck/pn/p∗∑i=0kmodpCinmodp $$\sum_{i=0}^kC_n^i=\sum_{i=0}^kC_{n/p}^{i/p}*C_{n\bmod p}^{i\bmod p}=\sum_{i=0}^{k/p-1}C_{n/p}^i*\sum_{j=0}^{p-1}C_{n\bmod p}^j+C_{n/p}^{k/p}*\sum_{i=0}^{k\bmod p}C_{n\bmod p}^i$$
至于 ∑i=0k/p−1Cin/p $\sum\limits_{i=0}^{k/p-1}C_{n/p}^i$可以递归处理，其余两个 ∑ $\sum$直接预处理即可。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;typedef long long LL;const int MOD=2333;int c[MOD][MOD],s[MOD][MOD];int get_c(LL n,LL m)
{if (n<m) return 0;if (!n) return 1;return get_c(n/MOD,m/MOD)*c[n%MOD][m%MOD]%MOD;
}int solve(LL n,LL k)
{if (k<0) return 0;if (!n) return 1;return (solve(n/MOD,k/MOD-1)*s[n%MOD][MOD-1]+get_c(n/MOD,k/MOD)*s[n%MOD][k%MOD])%MOD;
}int main()
{c[0][0]=1;for (int i=1;i<MOD;i++){c[i][0]=1;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<MOD;i++){s[i][0]=1;for (int j=1;j<MOD;j++) s[i][j]=(s[i][j-1]+c[i][j])%MOD;}int T;scanf("%d",&T);while (T--){LL n,k;scanf("%lld%lld",&n,&k);printf("%d\n",solve(n,k));}return 0;
}