[SHOI2015]超能粒子炮·改

[题目链接]

[思路要点]

看到组合数模数是 (2333) 这样一个小质数，很容易想到 (mathrm{Lucas}) 定理

但是如果直接按 (2333) 进制分解，发现没法做了，于是我们使用 $C_a^b % p = C_{frac a p}^{frac b p} cdot C_{a m%}^{b mod%mod p%
令 (f(n,k) = sum_{i=0}^{k} C_n^i)，那么要求的就是 (f(n,k))

[egin{align} f(n, k) &= sum_{i=0}^{k} C_{n}^i\ &= sum_{i=0}^{k} C_{frac n p}^{frac i p} cdot C_{n \% p}^{i \% p} \ &= sum_{i=0}^{frac k p - 1}C_{frac n p}^ i cdot left ( sum _{j = 0}^{p-1}C_{n \% p}^{j} ight)+C_{frac n p}^{frac k p}sum_{j=0}^{k\% p}C_{n \% p}^{j}\ &=f(frac n p, frac k p - 1) cdot f(n \% p, p - 1)+ C_{frac n p}^{frac kp}f(n \% p,k \% p) end{align} ]

由于 (p) 是 (2333)，我们可以把 (f(n\% p,p-1)) 和 (f(n\% p, k\% p)) 都预处理出来，然后递归求解，(C_{frac n p}^{frac k p}) 使用 (mathrm{Lucas}) 求解。

每次 (n) 会除以一个 (p)，所以复杂度 (mathcal{O}(p^2+Tcdot log_p^2n))

[代码]

#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
",F(n,k));
    }
    return 0;
}