题解 P4345 【[SHOI2015]超能粒子炮·改】

· · 题解

就是运用Lucas推一个柿子

首先是前置芝士Lucas定理

C_{n}^{m}\%p=C_{n/p}^{m/p}*C_{n\%p}^{m\%p}\%p

至于证明

我建议去问一下Lucas本人

至于这道题，我们要求的是这个柿子

\sum_{i=0}^kC_{n}^i\%p

于是我们设f(n,k)=\sum_{i=0}^kC_{n}^i

我们就可以化柿子啦

f(n,k)=\sum_{i=0}^kC_{n}^i \text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }=\sum_{i=0}^kC_{n/p}^{i/p}*C_{n\%p}^{i\%p}

这个东西一看就很熟悉，n/p啊，显然跟整除分块差不多啊

=C_{n/p}^0\sum_{i=0}^{p-1}C_{n\%p}^i+C_{n/p}^1\sum_{i=0}^{p-1}C_{n\%p}^i+...+C_{n/p}^{k/p}\sum_{i=0}^{k\%p}C_{n\%p}^i

前面有0到k/p-1这些个整块，于是我们可以将\sum_{i=0}^{p-1}C_{n\%p}^i提出来

变成

\sum_{i=0}^{p-1}C_{n\%p}^i*(C_{n/p}^0+C_{n/p}^1+...C_{n/p}^{k/p-1})

那这个东西岂不是可以写成

f(n\%p,p-1)*f(n/p,k/p-1)

在加上那个不完整的块

\sum_{i=0}^{k\%p}C_{n\%p}^i$可以写成$f(n\%p,k\%p)

于是就有

f(n,k)=f(n\%p,p-1)*f(n/p,k/p-1)+C_{n/p}^{k/p}*f(n\%p,k\%p)

由于n\%p还有k\%p都小于2333，所以f(n\%p,p-1)还有f(n\%p,k\%p)可以直接预处理好可以直接求出来

至于那个C_{n/p}^{k/p}就直接上Lucas好了

时间复杂度O(p^2+Tlog_{2333}^2n)

代码

非常sb的把C_0^0当成0WA了好几发

#include<iostream>
#include<cstring>
#include<cstdio>
#define re register
#define LL long long
#define maxn 2335
const int P=2333;
LL c[maxn+2][maxn+2];
LL f[maxn+2][maxn+2];
inline LL Lucas(LL n,LL m)
{
    if(!m) return 1;
    if(n==m) return 1;
    if(n<m) return 0;
    return c[n%P][m%P]*Lucas(n/P,m/P)%P;
}
inline LL F(LL n,LL k)
{
    if(k<0) return 0;
    if(!n) return 1;
    if(!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()
{
    int T;
    scanf("%d",&T);
    c[0][0]=1;
    for(re int i=1;i<=maxn;i++) 
        c[i][i]=c[i][0]=1;
    for(re int i=1;i<=maxn;i++)
        for(re int j=1;j<i;j++)
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%P;
    f[0][0]=1;
    for(re int i=1;i<=maxn;i++) 
        f[i][0]=1;
    for(re int i=0;i<=maxn;i++)
        for(re int j=1;j<=maxn;j++)
            f[i][j]=(c[i][j]+f[i][j-1])%P;
    LL n,k;
    while(T--)
    {
        scanf("%lld%lld",&n,&k);
        printf("%lld\n",F(n,k));
    }
    return 0;
}