SHOI 2015 BeyondGun

屑题

$T$组数据 求 $\sum_{i = 0}^{k}{C_n^i} (mod \space2333)$ 其中 t <= 1e5, n, k <= 1e18….

设$f(n,k) = \sum_{i = 0}^{k}{C_n^i} (mod \space2333)$ 然后用卢卡斯展开一下

得到

然后把那个小块暴力算掉就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<cstdio>
#include<cstring>
#include<iostream>

typedef long long ll;
const ll p = 2333;
const int N = 3e3 + 7;
ll C[N][N], f[N][N];

inline ll Lucas (ll m, ll n) {
if (!n || n == m || !m) return 1;
if (m < n) return 0;
return (C[m % p][n % p] * Lucas (m / p, n / p)) % p;
}
inline ll func (ll n, ll k) {
if (k < 0) return 0;
if (!n || !k) return 1;
if (n < p && k < p) return f[n][k];
return (func(n / p, k / p - 1) * f[n % p][p - 1] % p
+ Lucas (n / p, k / p) * f[n % p][k % p] % p) % p;
}

int main () {
int T; ll n, k;
scanf ("%d", &T);
C[0][0] = 1;
for (int i = 1; i <= p + 2; i++) {
C[i][0] = 1;
for (int j = 1; j <= i; j++)
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % p;
} //f[0][0] = 1;
for (int i = 0; i <= p + 2; i++) f[i][0] = 1;
for (int i = 0; i <= p + 2; i++) for (int j = 1; j <= p + 2; j++)
f[i][j] = (C[i][j] + f[i][j - 1]) % p;
while (T--) {
scanf ("%lld%lld", &n, &k);
printf ("%lld\n", func(n, k) % p);
}
return 0;
}