【题解】[SHOI2015] 超能粒子炮·改组合数学+lucas 定理 luoguP4345 —QIuly

显然，题目需要我们求出：

$\sum\limits_{i=0}^{k}C_{n}^{i} \mathbin{\mathrm{mod}} 2333$

其中 $n\leq 10^{18}$ 。直接暴力求显然会炸掉，感觉当前的式子不是很好做，推推式子看看。

首先 $2333$ 是质数，这个时候看到了组合数，应该是可以想到 $Lucas$ 定理的，我们将 $Lucas$ 套上去 (并且令 $p$ 为 $2333$ ) ，并且设答案为 $f(n,k)$ ：

$\begin{aligned} f(n,k)&=\sum\limits_{i=0}^{k}C_{n}^{i} \mathbin{\mathrm{mod}} p\\ &=\sum\limits_{i=0}^{k}C_{n\%p}^{i\%p}\cdot C_{n/p}^{i/p} \mathbin{\mathrm{mod}} p\\ &=\sum\limits_{x=0}^{p-1}C_{n\%p}^{x}\cdot \sum_{i=0}^{k}[i\%p=x]C_{n/p}^{i/p} \mathbin{\mathrm{mod}} p\\ &=C_{n/p}^{0}\sum\limits_{x=0}^{p-1}C_{n\%p}^{x}+C_{n/p}^{1}\sum\limits_{x=0}^{p-1}C_{n\%p}^{x}\cdots C_{n/p}^{k/p}\sum\limits_{x=0}^{k\%p} C_{n\%p}^{x}\mathbin{\mathrm{mod}}p\\ &=\sum\limits_{i=0}^{k/p-1}C_{n/p}^{i}\cdot \sum\limits_{x=0}^{p-1}C_{n\%p}^{x}+C_{n/p}^{k/p}\sum\limits_{x=0}^{k\%p}C_{n\%p}^{x}\mathbin{\mathrm{mod}}p\\ &=f(n/p,k/p-1)\cdot f(n\%p,p-1)+C_{n/p}^{k/p}\cdot f(n\%p,k\%p)\mathbin{\mathrm{mod}}p\\ \end{aligned}$
于是最终得到了答案，递归处理即可。

Code：

#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=2333+2;
#define p 2333

ll n,k,f[N][N],c[N][N];

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

ll lucas(ll n,ll m) {
    if(!m||n==m) return 1;
    if(n<m) return 0;
    if(n<p&&m<p) return c[n][m];
    return c[n%p][m%p]*lucas(n/p,m/p)%p;
}
ll F(ll n,ll k) {
    if(k<0) return 0;
    if(!n||!k) return 1;
    if(n<p&&k<p) return f[n][k];
    return (F(n/p,k/p-1)*f[n%p][p-1]%p+lucas(n/p,k/p)*f[n%p][k%p]%p)%p;
}

int main() {
    for(int i=0;i<=p;++i) c[i][0]=c[i][i]=1,f[i][0]=1;
    for(int i=1;i<=p;++i) for(int j=1;j<i;++j)
        c[i][j]=(c[i-1][j]+c[i-1][j-1])%p;
    for(int i=0;i<=p;++i) for(int j=1;j<=p;++j)
        f[i][j]=(f[i][j-1]+c[i][j])%p;
    int t;IN(t);
    while(t--) {
        IN(n),IN(k);
        printf("%lld\n",F(n,k));
    }
    return 0;
}

【题解】[SHOI2015] 超能粒子炮·改组合数学+lucas 定理 luoguP4345 —QIuly

于2019年5月30日2019年5月30日由Qiuly发布

Code：

Qiuly

0 条评论

发表回复取消回复

【题解】[SHOI2015] 超能粒子炮·改 组合数学+lucas 定理 luoguP4345 —QIuly

于2019年5月30日2019年5月30日由Qiuly发布

Code：

Qiuly

0 条评论

发表回复 取消回复

【题解】[SHOI2015] 超能粒子炮·改组合数学+lucas 定理 luoguP4345 —QIuly

发表回复取消回复