C++14(g++5.4) 解法, 执行用时: 259ms, 内存消耗: 73440K, 提交时间: 2019-08-09 11:28:46

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll const mod = 2333;
ll n,k,c[mod+10][mod+10],sum[mod+10][mod+10];
void Init(){
	for(ll i=0;i<=mod;i++){
		sum[i][0] = c[i][0] = 1;
		for(ll j=1;j<=i;j++){
			c[i][j] = (c[i-1][j-1] + c[i-1][j]) % mod;
		}
		for(ll j=1;j<=mod;j++)
			sum[i][j] = (sum[i][j-1] + c[i][j]) % mod;
	}
}
ll Lucas(ll n,ll m){
	if(n < m)	return 0;
	else if(m == 0)	return 1;
	else return c[n % mod][m % mod] * Lucas(n / mod,m / mod) % mod;
}
ll fun(ll n,ll k){
	if(k < 0)	return 0;
	if(n == 0)	return 1;
	return (sum[n % mod][mod - 1] * fun(n / mod,k / mod - 1) % mod + Lucas(n / mod,k / mod) * sum[n % mod][k % mod] % mod) % mod;
}
int main(){
	int T;
	Init();
	scanf("%d",&T);
	while(T--){
		scanf("%lld%lld",&n,&k);
		printf("%lld\n",fun(n,k));
	}
	return 0;
}

C++(clang++11) 解法, 执行用时: 180ms, 内存消耗: 73276K, 提交时间: 2020-11-01 09:21:17

#include<cstdio> 
#define ll long long
#define rep(i,x,y) for(ll i=x;i<=y;i++)
using namespace std; 
const ll maxn=2335,p=2333; 
ll c[maxn+2][maxn+2],f[maxn+2][maxn+2],T; 
inline ll lucas(ll n,ll m){
	if (m==0||n==m) return 1; 
	if (n<m) return 0; 
	return lucas(n/p,m/p)*c[n%p][m%p]%p; 
}
inline ll F(ll n,ll k){
	if (!n||!k) return 1; 
	if (k<0) return 0; 
	if (n<p&&k<p) return f[n][k]; 
    return (F(n/p,k/p-1)*f[n%p][p-1]%p+lucas(n/p,k/p)*f[n%p][k%p])%p; 
}
int main(){
	scanf("%lld",&T);
	c[0][0]=f[0][0]=1;  ll n,k; 
	rep(i,1,maxn) c[i][i]=c[i][0]=1; 
	rep(i,1,maxn) f[i][0]=1;
	rep(i,1,maxn) rep(j,1,i-1) c[i][j]=(c[i-1][j]+c[i-1][j-1])%p; 
	rep(i,0,maxn) rep(j,1,maxn) f[i][j]=(c[i][j]+f[i][j-1])%p;
	while (T--){
		scanf("%lld%lld",&n,&k); 
		printf("%lld\n",F(n,k)); 
	}
}