首先我们要明确题目要我们求的是这个式子：
[sum_{i = 0}^kC_n^i
]
我们先从部分分看起：
10分
预处理出组合数暴力算就是了。复杂度(O(N^2))
50分 --- 1
由于我们要求的东西是在杨辉三角的一行，所以我们可以递推求出改行组合数，递推式为(C_n^{m + 1} = C_n^m * frac{n - m}{m + 1})，证明的话就用组合数的定义式即可。复杂度(O(k))
50分 --- 2
这一档对正解有一定启发意义
跟据Lucas定理（什么你还不会Lucas？？？）
[C_n^i \% p = C_{n \% p}^{i \% p} * C_{n / p}^{i / p} \% p
]
我们可以将原式化成：
[sum_{i = 0}^{k} C_{n \% p}^{i \% p} * C_{n / p}^{i / p} \% p
]
等一下，(i / p)和(n / p)有循环节， (i / p)和(n / p)在很多时候都是相等的啊！
于是我们可以自然地想到：记
[f[j] = sum_{i = 0}^{j} C_{n \% p}^{i \% p} \% p
]
由于p不是很大，所以我们可以预处理出f数组
于是我们的复杂度可以从$O(t * 10^{18} * (卢卡斯复杂度))(优化成)O(t * k * (卢卡斯复杂度) / 2333)$
(Code:)
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
#define int long long
il int read() {
re int x = 0, f = 1; re char c = getchar();
while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
return x * f;
}
#define p 2333
#define rep(i, s, t) for(re int i = s; i <= t; ++ i)
#define maxn 3000
int n, m, c[maxn][maxn], f[maxn][maxn], ans, k;
il int Lucas(int n, int m) {
if(!m || n == m) return 1;
if(n < m) return 0;
return Lucas(n / p, m / p) * c[n % p][m % p] % p;
}
signed main() {
c[0][0] = f[0][0] = 1;
rep(i, 1, p) {
f[i][0] = c[i][0] = c[i][i] = 1;
rep(j, 1, i - 1) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % p;
rep(j, 1, i) f[i][j] = (f[i][j - 1] + c[i][j]) % p;
}
int T = read();
while(T --) {
n = read(), m = read(), ans = k = 0;
for(; k <= m - p; k += p) ans = (ans + f[n % p][n % p] * Lucas(n / p, k / p)) % p;
printf("%lld
", (ans + Lucas(n / p, k / p) * f[n % p][min(n % p, m % p)]) % p);
}
return 0;
}
100分
我们再来思考我们50-2慢在了哪里？
我们在算
for(; k <= m - p; k += p) ans = (ans + f[n % p][n % p] * Lucas(n / p, k / p)) % p;
的时候时间复杂度开销很大，但是我们如果提出(f[n \% p][n \% p])，柿子就成
[sum_{i = 0}^{m / p}C_{n / p}^i
]
哎，这部可以递归算吗？
所以我们可以推出：
[F(i, j) = f[n \% p][n \% p] * F(frac{n}{p}, frac{m}{p} - 1) + Lucas(frac{n}{p}, frac{m}{p}) * f[n \% p][min(n \% p, m \% p)]
]
(Code:)
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
#define int long long
il int read() {
re int x = 0, f = 1; re char c = getchar();
while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
return x * f;
}
#define p 2333
#define rep(i, s, t) for(re int i = s; i <= t; ++ i)
#define maxn 3000
int n, m, c[maxn][maxn], f[maxn][maxn];
il int Lucas(int n, int m) {
if(!m || n == m) return 1;
if(n < m) return 0;
return Lucas(n / p, m / p) * c[n % p][m % p] % p;
}
il int F(int n, int m) {
if(m == -1) return 0;
if(!m) return 1;
if(n < p) return f[n][m];
return (f[n % p][n % p] * F(n / p, m / p - 1) + Lucas(n / p, m / p) * f[n % p][min(n % p, m % p)]) % p;
}
signed main() {
c[0][0] = f[0][0] = 1;
rep(i, 1, p) {
f[i][0] = c[i][0] = c[i][i] = 1;
rep(j, 1, i - 1) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % p;
rep(j, 1, p) f[i][j] = (f[i][j - 1] + c[i][j]) % p;
}
int T = read();
while(T --) {
n = read(), m = read();
printf("%lld
", F(n, m));
}
return 0;
}