题意

定义 $f(n,k) = \sum_{i=0}^k C_n^i$，$T$ 次询问，每次给你 $n,k$，求 $f(n,k) \bmod 2333$ 的值。

$1 \le T \le 10^5,1 \le n,k \le 10^{18}$。

分析

直接做是不可能的，直接 T 飞。从 $P = 2333$ 入手。这个模数是一个很小的质数。因为很小，可以预处理出 $f[i][j](0\le i,j < P)$，时间复杂度 $O(P^2)$。但是呢，$n,k$ 会很大。如果组合数参数很大，模数很小，可以考虑用 Lucas 定理。接下来拆式子。

$$f(n,k) = \sum_{i=0}^k C_n^i$$
$$= \sum_{i=0}^k C_{\left \lfloor n/P \right \rfloor}^{\left \lfloor i/P \right \rfloor}\times C_{n \bmod P}^{i \bmod P}$$

发现接下来不好拆了，考虑从整除入手。按照整除分块的思想，有 $m = \left \lfloor k/P \right \rfloor - 1$ 个整块和 $1$ 个散块。写算整块。

$$= C_{\left \lfloor n/P \right \rfloor}^0 \sum_{i=0}^{P-1} C_{n \bmod P}^i+C_{\left \lfloor n/P \right \rfloor}^1 \sum_{i=0}^{P-1} C_{n \bmod P}^i+\dots + C_{\left \lfloor n/P \right \rfloor}^m \sum_{i=0}^{P-1} C_{n \bmod P}^i$$
$$=\sum_{i=0}^{P-1} C_{n \bmod P}^i \times \sum_{i=0}^m C_{\left \lfloor n/P \right \rfloor}^i$$
$$=f(n \bmod P,P-1)\times f(\left \lfloor n/P \right \rfloor,m)$$
$$=f(n \bmod P,P-1)\times f(\left \lfloor n/P \right \rfloor,\left \lfloor k/P \right \rfloor-1)$$

这一部分前一项 $n \bmod P<P,P-1<P$，直接用预处理的。后一部分递归处理，最多 $O(\log_P k)$ 层。

还有散块。

$$C_{\left \lfloor n/P \right \rfloor}^{\left \lfloor k/P \right \rfloor} \times \sum_{i=0}^{k \bmod P} C_{n \bmod P}^i = C_{\left \lfloor n/P \right \rfloor}^{\left \lfloor k/P \right \rfloor} \times f(n \bmod P,k \bmod P)$$

同上，这里的后一项 $n \bmod P < P,k \bmod P < P$，可以直接用预处理的。

所以最后我们拆出来的式子如下。

$$f(n,k) = f(n \bmod P,P-1) \times f(\left \lfloor n/P \right \rfloor,\left \lfloor k/P \right \rfloor-1) + C_{\left \lfloor n/P \right \rfloor}^{\left \lfloor k/P \right \rfloor} \times f(n \bmod P,k \bmod P)$$

这个式子中，$f(\left \lfloor n/P \right \rfloor,\left \lfloor k/P \right \rfloor-1)$ 是递归求解，而 $C_{\left \lfloor n/P \right \rfloor}^{\left \lfloor k/P \right \rfloor}$ 要用 Lucas 定理 $O(\log_Pk)$ 求解。最后时间复杂度就是 $O(P^2 + T\log_P^2k)$。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
inline ll rd(){
    ll s = 0, w = 1;
    char ch = getchar();
    for (;ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
    for (;ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 1) + (s << 3) + ch - '0');
    return s * w;
}
const int P = 2333;
int C[P + 5][P + 5], f[P + 5][P + 5];
ll n, k;
int Lcs(ll n, ll m, int P){return (n < m ? 0 : !n ? 1 : 1ll * Lcs(n / P, m / P, P) * C[n % P][m % P] % P);}
int 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 (1ll * f[n % P][P - 1] * F(n / P, k / P - 1) % P + 1ll * Lcs(n / P, k / P, P) * f[n % P][k % P] % P) % P;
}
int main(){
    for (int i = 0; i < P; i++){
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; j++) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % P;
    }
    for (int i = 0; i < P; i++) f[i][0] = 1;
    for (int i = 0; i < P; i++) for (int j = 1; j < P; j++) f[i][j] = (f[i][j - 1] + C[i][j]) % P;
    for (int T = rd(); T--;) n = rd(), k = rd(), printf ("%d\n", F(n, k));
    return 0;
}