组合数学)"/>
[BZOJ4591][SHOI2015]超能粒子炮·改(Lucas+组合数学)
题目:
我是超链接
题解:
也就是求 ∑ki=0Cin(%mod) ∑ i = 0 k C n i ( % m o d )
n,k这么大,Lucas没跑了,我们先画柿子(模意义下
Smn S n m 意为 ∑mi=0Cin ∑ i = 0 m C n i
Lucas定理:
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 =∑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 =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[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));}
}
更多推荐
[BZOJ4591][SHOI2015]超能粒子炮·改(Lucas+组合数学)
发布评论