Qiuly

「SHOI2015」超能粒子炮·改 组合数学+lucas定理 luoguP4345
显然,题目需要我们求出:于是最终得到了答案,递归处理即可。Code:#include <queue> ...
扫描右侧二维码阅读全文
25
2019/05

「SHOI2015」超能粒子炮·改 组合数学+lucas定理 luoguP4345

显然,题目需要我们求出:

$$\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\\ &=\sum\limits_{x=0}^{p-1}C_{n\%p}^{x}\cdot \sum_{i=0}^{(k-x)/p}C_{n/p}^{i} \mathbin{\mathrm{mod}} p\\ &=\sum\limits_{x=0}^{p-1}C_{n\%p}^{x}\cdot f(n/p,(k-x)/p)\mathbin{\mathrm{mod}} p\\ \end{aligned} $$

好像不好处理......[汗],变个样式再看看。

$$ \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;
}
最后修改:2019 年 05 月 30 日 03 : 26 PM

发表评论