先看了一遍lucas，还是只能拿50分（似乎已经满足了）。

正解当然还是看某个大佬的啦。

我们要求的就是

\[f(n, k) = \sum _ {i = 0} ^ {k} C _ {n} ^ {i} \% p\]

然后根据lucas定理，就开始愉快的推式子了……

\[ \begin{align*} f(n, k) &= \sum _ {i = 0} ^ {k} C _ {n} ^ {i} \% p \\ &= \sum _ {i = 0} ^ {k} C_ {n / p} ^ {i / p} * C _ {n \% p} ^ {i \% p} \\ &= C_{n / p} ^ {0} \sum _ {i = 0} ^ {p - 1} C _ {n \% p} ^ {i} + C _ {n / p} ^ {1} \sum _ {i = 0} ^ {p - 1} C _ {n \% p} ^ {i} + \ldots + C_{n / p} ^ {k / p - 1} \sum _ {i = 0} ^ {p - 1} C _ {n \% p} ^ {i} + C _ {n / p} ^ {k / p} \sum _ {i = 0} ^ {k \% p} C _ {n \% p} ^ {i}\\ &= \sum _ {i = 0} ^ {p - 1} C _ {n \% p} ^ {i} * (C _ {n / p} ^ {0} + C_{n / p} ^ {1} + \ldots + C_{n / p} ^ {k / p - 1}) + C _ {n / p} ^ {k / p} \sum _ {i = 0} ^ {k \% p} C _ {n \% p} ^ {i} \\ &= f(n \% p, p - 1) * f(n / p, k / p - 1) + C _ {n / p} ^ {k / p} * f(n \% p, k \% p) \\ \end{align*} \]

然后把\(f(n \% p, k \% p)\)预处理一下，就完事了。（说的真轻松……）

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;#define enter puts("") #define space putchar(' ')#define Mem(a, x) memset(a, x, sizeof(a))#define In inlinetypedef long long ll;typedef double db;const int INF = 0x3f3f3f3f;const db eps = 1e-8;const int maxn = 2505;const int p = 2333;inline ll read(){ ll ans = 0; char ch = getchar(), last = ' '; while(!isdigit(ch)) last = ch, ch = getchar(); while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar(); if(last == '-') ans = -ans; return ans;}inline void write(ll x){ if(x < 0) x = -x, putchar('-'); if(x >= 10) write(x / 10); putchar(x % 10 + '0');}ll n, K;ll C[maxn][maxn], f[maxn][maxn];In ll inc(ll a, ll b) {return a + b >= p ? a + b - p : a + b;}In ll lucas(ll n, ll m){ if(!m || n == m) return 1; if(n < m) return 0; return C[n % p][m % p] * lucas(n / p, m / p) % p;}In ll F(ll n, ll K){ if(K < 0) return 0; if(!n || !K) return 1; if(n < p && K < p) return f[n][K]; return inc(f[n % p][p - 1] * F(n / p, K / p - 1) % p, lucas(n / p, K / p) * f[n % p][K % p] % p);}In void init(){ for(int i = 0; i < maxn; ++i) C[i][0] = 1; for(int i = 1; i < maxn; ++i) for(int j = 1; j <= i; ++j) C[i][j] = inc(C[i - 1][j - 1], C[i - 1][j]); for(int i = 0; i < maxn; ++i) f[i][0] = 1; for(int i = 0; i < maxn; ++i) for(int j = 1; j < maxn; ++j) f[i][j] = inc(C[i][j], f[i][j - 1]);}int main(){ init(); int T = read(); while(T--) { n = read(), K = read(); write(F(n, K)), enter; } return 0;}