分析

如果我们读完题发现我们要求的是这个 ，定义一个二元组 ，根据 定理，可以推导到

在一波无情的推式子之后，这道题就做完了。

代码

#include<bits/stdc++.h> 
using namespace std;
#define LL long long
LL read() {
    LL x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f=1;ch=getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f ? -x : x;
}
const LL P = 2333,N = 3010;
LL C[N][N],S[N][N];
LL Calc(LL n,LL m) {
    if(n < m) return 0;
    if(!m) return 1;
    return (Calc(n/P,m/P) * C[n%P][m%P]) % P;
}
LL F(LL n,LL k) {
    if(n < P) return S[n][k];
    LL res = (F(n/P,(k/P)-1) * F(n%P,P-1) % P + F(n%P,k%P) * Calc(n/P,k/P) % P) % P;
    res = (res % P + P) % P;
    return res;
}
LL n,k;
int main() {
    for(LL i = 0;i < P;i++) {
        LL j;
        for(C[i][0] = j = 1;j <= i;j++) {
            C[i][j] = (C[i-1][j] + C[i-1][j-1]) % P;
        }
        S[i][0] = C[i][0];
        for(j = 1;j < P;j++) {
            S[i][j] = (S[i][j-1] + C[i][j]) % P;
        }
    }
    LL T = read();
    while(T--) {
        n = read();k = read();
        printf("%lld\n",F(n,k));
    }
}