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;
}