分析

如果我们读完题发现我们要求的是这个 $ans=\sum_i^k{n \choose i} \bmod P$ ，定义一个二元组 $S(n,k)=\sum_i^k{n \choose i} \bmod P$ ，根据 $Lucas$ 定理，可以推导到

$\begin{align*} S(n,k)&=\sum_{i=0}^k {n\choose i}\\ &=\sum_{i=0}^k {n/p \choose i/p}*{n\%p \choose i\%p}\\ &=\sum_i^{p-1} {n\%p \choose i} * \sum_j^n[j\%p=i]{n/p \choose j/p} \\ &=\sum_{i=0}^{(k/p)-1} ({n/p\choose i}*\sum_{j=0}^{p-1} {n\%p \choose j})+\sum_{i=(k/p)*p}^{k} {n/p\choose i/p}*{n\%p \choose i\%p}\\ &=\sum_{i=0}^{(k/p)-1} {n/p\choose i}*\sum_{j=0}^{p-1} {n\%p \choose j}+\sum_{i=0}^{k\%p}{n\%p \choose i}*{n/p \choose k/p}\\ &=S(n/p,(k/p)-1)*S(n\%p,p-1)+S(n\%p,k\%p)*{n/p \choose k/p}. \end{align*}$
在一波无情的推式子之后，这道题就做完了。

代码

#include<bits/stdc++.h> 
using namespace std;
#define LL long long
LL read() {
    LL x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f=1;ch=getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f ? -x : x;
}
const LL P = 2333,N = 3010;
LL C[N][N],S[N][N];
LL Calc(LL n,LL m) {
    if(n < m) return 0;
    if(!m) return 1;
    return (Calc(n/P,m/P) * C[n%P][m%P]) % P;
}
LL F(LL n,LL k) {
    if(n < P) return S[n][k];
    LL res = (F(n/P,(k/P)-1) * F(n%P,P-1) % P + F(n%P,k%P) * Calc(n/P,k/P) % P) % P;
    res = (res % P + P) % P;
    return res;
}
LL n,k;
int main() {
    for(LL i = 0;i < P;i++) {
        LL j;
        for(C[i][0] = j = 1;j <= i;j++) {
            C[i][j] = (C[i-1][j] + C[i-1][j-1]) % P;
        }
        S[i][0] = C[i][0];
        for(j = 1;j < P;j++) {
            S[i][j] = (S[i][j-1] + C[i][j]) % P;
        }
    }
    LL T = read();
    while(T--) {
        n = read();k = read();
        printf("%lld\n",F(n,k));
    }
}

超能粒子炮 · 改

分析

代码