P4345 [SHOI2015]超能粒子炮·改

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#define ll long long
using namespace std;
const int mod=2333;
const int maxn=mod+2;
int sum[maxn][maxn];
int c[maxn][maxn];

void init(void)
{
    for(int i=0;i<=mod;i++)
        c[i][i]=c[i][0]=1,sum[i][0]=sum[0][i]=1;
    for(int i=1;i<=mod;i++)
    {
        for(int j=1;j<=i;j++)
        {
            c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;

        }
        for(int j=1;j<=mod;j++)
            sum[i][j]=(sum[i][j-1]+c[i][j])%mod;
    }
    return ;
}

ll mypow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=(ans*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return ans;
}

int Lucas(ll n,ll m)
{

    if(m==0) return 1;
    if(n<m) return 0;
    if(n<mod&&m<mod) return c[n][m];
    return c[n%mod][m%mod]*Lucas(n/mod,m/mod)%mod;
}

int ca(ll n,ll m)
{
    if(n<mod) return sum[n][m];
    return (sum[n%mod][mod-1]%mod*ca(n/mod,m/mod-1)%mod+Lucas(n/mod,m/mod)*sum[n%mod][m%mod])%mod;
}

int main(void)
{
    ll t;
    cin>>t;
    init();
    while(t--)
    {
        ll n,m;
        scanf("%lld%lld",&n,&m);
        printf("%d\n",ca(n,m));
    }
    return 0;
}