如何在取模的环境下快速处理组合数的前缀和？-526互联

我的代码：

#include<cstdio>
#include<algorithm>
#define p 2333
#define int long long
using namespace std;
int n,k,t,c[2335][2335],f[2335][2335];
int luc(int n,int m){
    if(!n)return 1;
    if(n<m)return 0;
    return (luc(n/p,m/p)*c[n%p][m%p])%p;
}
int fc(int n,int k){
    if(k<0)return 0;
    if(n==0)return 1;
    if(k==0)return 1;
    if(n<=p&&k<=p)return f[n][k];
    return ((fc(n/p,(k/p)-1)*fc(n%p,p-1)%p)+luc(n/p,k/p)*fc(n%p,k%p)%p)%p; 
}
signed main(){
    c[0][0]=1;
    for(int i=1;i<=2333;i++){
        c[i][0]=1;
        for(int j=1;j<=2333;j++)c[i][j]=(c[i-1][j]+c[i-1][j-1])%p;
    }
    f[0][0]=1;
    for(int i=1;i<=2333;i++){
        f[i][0]=1;
        for(int j=1;j<=2333;j++)f[i][j]=(f[i][j-1]+c[i][j])%p;
    }
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld",&n,&k);
        printf("%lld\n",fc(n,k));
    }
    return 0;
}

完结撒花

前缀