形式化题目

给定常数质数 $p = 2333$。有 $T$ 组询问，每次给定非负整数 $n, k$，求组合数前缀和：

正解

思路

根据 Lucas 定理，对于质数 $p$ 和任意非负整数 $n, i$，有：

我们要求的是前缀和：

将求和变量 $i$ 进行带余除法：设 $i = j \cdot p + r$，其中 $0 \le r < p$。由于 $0 \le i \le k$，可将商 $j$ 分成两部分考虑：

1. 完整块（$0 \le j \le \lfloor k/p \rfloor - 1$）： 在每一个固定的 $j$ 下，余数 $r$ 取遍了完整区间 $[0, p-1]$。利用 Lucas 定理将组合数因式分解：

   $$\sum_{r=0}^{p-1} \binom{n}{j \cdot p + r} \equiv \binom{\lfloor n/p \rfloor}{j} \sum_{r=0}^{p-1} \binom{n \bmod p}{r} = \binom{\lfloor n/p \rfloor}{j} S(n \bmod p, p-1) \pmod p$$

   对所有合法的 $j$ 求和，提取公因式 $S(n \bmod p, p-1)$：

   $$\sum_{j=0}^{\lfloor k/p \rfloor - 1} \left( \binom{\lfloor n/p \rfloor}{j} S(n \bmod p, p-1) \right) = S(n \bmod p, p-1) \cdot S\left(\lfloor n/p \rfloor, \lfloor k/p \rfloor - 1\right) \pmod p$$

2. 不完整散块（$j = \lfloor k/p \rfloor$）： 此时商固定为 $\lfloor k/p \rfloor$，余数 $r$ 只能取到 $0 \le r \le k \bmod p$。其贡献为：

   $$\binom{\lfloor n/p \rfloor}{\lfloor k/p \rfloor} \sum_{r=0}^{k \bmod p} \binom{n \bmod p}{r} = \binom{\lfloor n/p \rfloor}{\lfloor k/p \rfloor} \cdot S(n \bmod p, k \bmod p) \pmod p$$

将两部分合并，即可得到核心递归公式：

算法流程

1. 预处理：模数 $p = 2333$ 很小，利用杨辉三角预处理出 $p \times p$ 的组合数表 $C(n, m) \pmod p$ 和每行前缀和表 $S(n, m) \pmod p$。
2. 递归计算：
   • 递归边界：若 $k < 0$，返回 $0$；若 $n < p$ 且 $k < p$，直接查表返回 $S[n][k]$。
   • 转移时调用自身计算更小规模的 $S(\lfloor n/p \rfloor, \lfloor k/p \rfloor - 1)$，并用 Lucas 定理单次查询 $\binom{\lfloor n/p \rfloor}{\lfloor k/p \rfloor}$。

代码

Python 版：

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 00:22
# update_at: 2026-10-01 00:22

import sys

P = 2333  # 模数，题目给定质数


def init_tables() -> tuple[list[list[int]], list[list[int]]]:
    """预处理模 P 下的杨辉三角组合数表与行前缀和表。"""
    c = [[0] * P for _ in range(P)]
    s = [[0] * P for _ in range(P)]
    for i in range(P):
        c[i][0] = 1
        s[i][0] = 1
        for j in range(1, i + 1):
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % P
            s[i][j] = (s[i][j - 1] + c[i][j]) % P
        for j in range(i + 1, P):
            s[i][j] = s[i][i]
    return c, s


C, S = init_tables()


def lucas(n: int, m: int) -> int:
    """计算 Lucas 定理下的组合数 C(n, m) mod P。"""
    if m == 0:
        return 1
    if n < m:
        return 0
    if n < P and m < P:
        return C[n][m]
    return lucas(n // P, m // P) * C[n % P][m % P] % P


def query_sum(n: int, k: int) -> int:
    """计算前缀组合数和 S(n, k) = sum_{i=0}^k C(n, i) mod P。"""
    if k < 0:
        return 0
    if n < P and k < P:
        return S[n][k]
    # Lucas 递归展开：整除整块部分乘以对应前缀和 + 散块部分
    full_blocks = S[n % P][P - 1] * query_sum(n // P, k // P - 1)
    partial_block = lucas(n // P, k // P) * S[n % P][k % P]
    return (full_blocks + partial_block) % P


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    T = next(data)

    for _ in range(T):
        n = next(data)
        k = next(data)
        out.append(str(query_sum(n, k)))

    sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 00:55
 * update_at: 2026-10-06 00:55
 */

#include <cstdio>

typedef long long ll;

const ll P = 2333;            // 模数，题目给定的质数
const ll MOD = 2333;

// C[n][m]：模 2333 意义下的组合数表，n, m < 2333
// S[n][m]：组合数表第 n 行的前缀和 S(n, m) = sum_{i=0}^{m} C(n, i) mod 2333
// 值都小于 2333，用 int 控制内存（两张表共约 44MB）
int C[P][P];
int S[P][P];

// 预处理杨辉三角组合数表与行前缀和表（i 从 0 开始，第 0 行也要填）
void init() {
    for (ll i = 0; i < P; i++) {
        C[i][0] = 1;
        S[i][0] = 1;
        for (ll j = 1; j <= i; j++)
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
        // 第 i 行 C(i, j) 在 j > i 时为 0，前缀和保持不变
        for (ll j = 1; j < P; j++) {
            if (j <= i)
                S[i][j] = (S[i][j - 1] + C[i][j]) % MOD;
            else
                S[i][j] = S[i][i];
        }
    }
}

// Lucas 定理求 C(n, m) mod 2333
ll lucas(ll n, ll m) {
    if (m == 0) return 1;
    if (n < m) return 0;
    if (n < P && m < P) return C[n][m];
    return lucas(n / P, m / P) * C[n % P][m % P] % MOD;
}

// 求 S(n, k) = sum_{i=0}^{k} C(n, i) mod 2333
// 按 i = j*p + r 分块：完整块贡献 S(n%P, P-1) * S(n/P, k/P-1)，
// 散块（j = k/P，r 只到 k%P）贡献 C(n/P, k/P) * S(n%P, k%P)
ll query_sum(ll n, ll k) {
    if (k < 0) return 0;
    if (n < P && k < P) return S[n][k];
    ll full = S[n % P][P - 1] * query_sum(n / P, k / P - 1) % MOD;
    ll part = lucas(n / P, k / P) * S[n % P][k % P] % MOD;
    return (full + part) % MOD;
}

int main() {
    init();
    ll t;
    scanf("%lld", &t);
    while (t--) {
        ll n, k;
        scanf("%lld%lld", &n, &k);
        printf("%lld\n", query_sum(n, k));
    }
    return 0;
}

复杂度

• 时间复杂度：
  • 预处理表格：时间复杂度为 $O(p^2) = 2333^2 \approx 5.4 \times 10^6$ 次运算。
  • 单次查询：每层递归规模以 $p$ 为底对数缩小，递归深度为 $\lfloor \log_p n \rfloor$。由于 $p = 2333, n \le 10^{18}$，递归层数最多不超过 $6$ 层。每次递归需要一次 $O(\log_p n)$ 的 Lucas 组合数求值与一次子问题递归调用，单次查询时间复杂度为 $O(\log_p^2 n)$。
  • 总时间复杂度为 $O(p^2 + T \log_p^2 n)$。
• 空间复杂度：预处理存储 $p \times p$ 的组合数表和前缀和表，空间复杂度为 $O(p^2)$。

总结

本题是 Lucas 定理在组合数前缀和求值中的经典应用。通过将下标 $i$ 按模 $p$ 进行整块与散块分解，巧妙地将上指标与下指标同时缩小除以 $p$，从而把原本 $O(k)$ 的不可行前缀求和优化为 $O(\log_p^2 n)$ 的分治递归。