超能粒子炮 · 改

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 2011 字
给定n、k，求Σ_{i=0}^{k}C对23
一本通
练习
正文

/*
原题：T1658「一本通 6.6 练习 7」超能粒子炮 · 改
题意：给定 n、k，求 Σ_{i=0}^{k} C(n,i) 对 2333 取模的结果。
思路：记 S(n,k)=Σ_{i=0}^{k}C(n,i)，令 n=n1·p+n0、k=k1·p+k0（p=2333）。
由 Lucas 定理拆分后整理得递推式：
S(n,k) = 2^{n0}·S(n1, k1-1) + C(n1,k1)·S(n0,k0)   (mod p)
其中 2^{n0} 来自 Σ_{i=0}^{p-1}C(n0,i)=2^{n0}。
边界：k<0 时为 0；k≥n 时为 2^n；n<p 时直接查预处理好的组合数前缀和。
复杂度：时间 O(log_p n)，空间 O(p^2) 存 2333 以内的杨辉三角
易错点：1) p=2333 较小，预处理二维数组要用全局变量而非栈上局部数组；
2) 递推式第一项是 2^{n0} 乘 S(n1,k1-1)，第二项才乘上面的组合数，别弄反；
3) k≥n 时必须先返回 2^n，否则 C(n1,k1) 会越界成 0 而漏算。
*/
#include <bits/stdc++.h>
using namespace std;
const int P=2333;
static int cc[P][P];
long long qpow(long long a,long long n){
    long long r=1;
    a%=P;
    while(n>0){
        if(n&1){
            r=r*a%P;
        }
        a=a*a%P;
        n>>=1;
    }
    return r;
}
long long combSmall(long long n,long long m){
    if(m<0 || m>n){
        return 0;
    }
    return cc[n][m];
}
long long lucasC(long long n,long long m){
    if(m<0 || m>n){
        return 0;
    }
    long long res=1;
    while(n>0 || m>0){
        res=res*combSmall(n%P,m%P)%P;
        n/=P;
        m/=P;
    }
    return res;
}
long long rowPrefix(int n,int k){
    if(k>n){
        k=n;
    }
    long long s=0;
    for(int i=0;i<=k;i++){
        s=(s+cc[n][i])%P;
    }
    return s;
}
long long S(long long n,long long k){
    if(k<0){
        return 0;
    }
    if(k>=n){
        return qpow(2,n);
    }
    if(n<P){
        return rowPrefix((int)n,(int)k);
    }
    long long n1=n/P;
    long long n0=n%P;
    long long k1=k/P;
    long long k0=k%P;
    long long part1=S(n1,k1-1)*qpow(2,n0)%P;
    long long part2=lucasC(n1,k1)*rowPrefix((int)n0,(int)k0)%P;
    return (part1+part2)%P;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    for(int i=0;i<P;i++){
        cc[i][0]=1;
        cc[i][i]=1;
        for(int j=1;j<i;j++){
            cc[i][j]=(cc[i-1][j-1]+cc[i-1][j])%P;
        }
    }
    int t;
    cin>>t;
    while(t--){
        long long n,k;
        cin>>n>>k;
        cout<<S(n,k)<<"\n";
    }
    return 0;
}
超能粒子炮 · 改

正文

一本通·提高篇的其它内容
