[BZOJ4591][SHOI2015]超能粒子炮·改（Lucas+组合数学）

组合数学）"/>

[BZOJ4591][SHOI2015]超能粒子炮·改（Lucas+组合数学）

题目：

我是超链接

题解：

也就是求 ∑ki=0Cin(%mod) ∑ i = 0 k C n i ( % m o d ) $\sum_{i=0}^{k}C_n^i(\% mod)$
n,k这么大，Lucas没跑了，我们先画柿子（模意义下
Smn S n m $S_n^m$意为 ∑mi=0Cin ∑ i = 0 m C n i $\sum_{i=0}^{m}C_n^i$
Lucas定理：

Skn=∑i=0kCin=∑i=0k(Ci%pn%p∗Ci/pn/p) S n k = ∑ i = 0 k C n i = ∑ i = 0 k ( C n % p i % p ∗ C n / p i / p ) $$S_{n}^{k}=\sum_{i=0}^{k}C_n^i=\sum_{i=0}^{k}(C_{n\% p}^{i\% p}*C_{n/p}^{i/p})$$
i=ip
=∑i=0k/p−1(Cin/p∗∑j=0p−1Cjn%p)+Ck/pn/p∗∑i=0k%pCin%p = ∑ i = 0 k / p − 1 ( C n / p i ∗ ∑ j = 0 p − 1 C n % p j ) + C n / p k / p ∗ ∑ i = 0 k % p C n % p i $$=\sum_{i=0}^{k/p-1}(C_{n/p}^i*\sum _{j=0}^{p-1}C_{n\% p}^{j})+C_{n/p}^{k/p}*\sum_{i=0}^{k\% p}C_{n\% p}^{i}$$

=∑i=0k/p−1Cin/p∗Sp−1n%p+Ck/pn/p∗Sk%pn%p = ∑ i = 0 k / p − 1 C n / p i ∗ S n % p p − 1 + C n / p k / p ∗ S n % p k % p $$=\sum_{i=0}^{k/p-1}C_{n/p}^i*S_{n\% p}^{p-1}+C_{n/p}^{k/p}*S_{n\% p}^{k\% p}$$ =Sk/p−1n/p∗Sp−1n%p+Ck/pn/p∗Sk%pn%p = S n / p k / p − 1 ∗ S n % p p − 1 + C n / p k / p ∗ S n % p k % p $$=S_{n/p}^{k/p-1}*S_{n\% p}^{p-1}+C_{n/p}^{k/p}*S_{n\% p}^{k\% p}$$
我们预处理就好了
注意两个问题，一个是s[0][i]=1，另一个是要时时刻刻注意s的意义，当m>n的时候s并不是0= =

代码：

#include <cstdio>
#define LL long long 
using namespace std;
const int p=2333;
int c[p+5][p+5],s[p+5][p+5];
LL Lucas(LL n,LL m)
{if (!m) return 1;if (n<m) return 0; LL ans=1;for (;m;n/=p,m/=p) ans=ans*c[n%p][m%p]%p;return ans;
}
LL askS(LL n,LL k)
{if (n<p) return s[n][k];LL ans=(s[n%p][p-1]*askS(n/p,k/p-1)%p+Lucas(n/p,k/p)*s[n%p][k%p]%p)%p;return ans;
}
void init()
{c[0][0]=1;for (int i=0;i<p;i++) s[0][i]=1;for (int i=1;i<p;i++) {c[i][0]=1,s[i][0]=1;for (int j=1;j<p;j++) {c[i][j]=(c[i-1][j]+c[i-1][j-1])%p;s[i][j]=(s[i][j-1]+c[i][j])%p;}}
}
int main()
{init();int T;scanf("%d",&T);while (T--){LL n,k;scanf("%lld%lld",&n,&k);printf("%lld\n",askS(n,k));}
}