Description

给定n，k，求 $(\sum\limits_{i=0}^{k}{C_n^i})\ mod\ 2333$

Solution

首先，我们要用到卢卡斯定理：$$C_n^m\ mod\ p=C_{n/p}^{m/p}*C_{n\ mod\ p}^{m\ mod\ p}\ mod\ p$$

我们要求解的是$$(\sum\limits_{i=0}^{k}{C_n^i})\ mod\ 2333$$

我们定义$f(n,k)=\sum\limits_{i=0}^{k}{C_n^i}$

由卢卡斯定理可知$$\sum\limits_{i=0}^{k}{C_n^i}=\sum\limits_{i=0}^{k}{C_{n/p}^{i/p}*C_{n\ mod\ p}^{i\ mod\ p}}$$

根据整除分块（数论分块）,可得

$$=C_{n/p}^0\sum\limits_{i=0}^{p-1}{C_{n\ mod\ p}^i} + C_{n/p}^1\sum\limits_{i=0}^{p-1}{C_{n\ mod\ p}^i}+C_{n/p}^2\sum\limits_{i=0}^{p-1}{C_{n\ mod\ p}^i}+...+C_{n/p}^{k/p}\sum\limits_{i=0}^{k\ mod\ p}{C_{n\ mod\ p}^i}$$

提取公因式，得

$$=\sum\limits_{i=0}^{p-1}{C_{n\ mod\ p}^i}*({C_{n/p}^0+C_{n/p}^1+...+C_{n/p}^{k/{p-1}}})=f(n\ mod\ p, p-1)*f(n/p,k/p-1)$$

加上最后不完整的一块，得

$$f(n,k)=f(n\ mod\ p, p-1)*f(n/p,k/p-1)+C_{n/p}^{k/p}*f(n\ mod\ p, k\ mod\ p)$$

取模之后的值肯定小于2333，我们可以直接预处理[0,2333]之间的C和f,组合数使用Lucas计算，时间复杂度为$O(p^2+Tlog_{2333}^2n)$

Code

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int mod = 2333;
 5 ll C[2340][2340], f[2340][2340];
 6 ll Locas(ll n, ll m) {
 7     if (m == 0) return 1;
 8     if (n == m) return 1;
 9     if (n < m) return 0;
10     return Locas(n / mod, m / mod) * C[n % mod][m % mod] % mod;
11 }
12 ll calc(ll x, ll y) {
13     if (y < 0) return 0;
14     if (!x || !y) return 1;
15     if (x < mod && y < mod) return f[x][y];
16     return (calc(x / mod, y / mod - 1) * f[x % mod][mod - 1] % mod + Locas(x / mod, y / mod) * f[x % mod][y % mod] % mod) % mod;
17 }
18 int main() {
19     for (register int i = 0; i <= 2335; ++i) C[i][i] = C[i][0] = 1;
20      for (register int i = 1; i <= 2335; ++i)
21         for (register int j = 1; j < i; ++j)
22             C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
23     for (register int i = 0; i <= 2335; ++i) f[i][0] = 1;
24     for (register int i = 0; i <= 2335; ++i)
25         for (register int j = 1; j <= 2335; ++j)
26             f[i][j] = (C[i][j] + f[i][j - 1]) % mod;
27     int T;
28     scanf("%d", &T);
29     while (T--) {
30         ll n, k;
31         scanf("%lld%lld", &n, &k);
32         printf("%lld\n", calc(n, k));
33     }
34     return 0;
35 }

AC Code