[NOIP 2016 提高组] 组合数问题

题意

给定固定的 $k$ 和 $t$ 组询问。每组询问给出 $n,m$ ，要求统计多少对 $(i,j)$ 满足：

0\leqslant i\leqslant n,\qquad 0\leqslant j\leqslant\min(i,m),\qquad k\mid\binom{i}{j}.

其中 $n,m\leqslant 2000$ ，询问数 $t\leqslant 10^4$ 。

思路

朴素做法的瓶颈

小数据可以先递推组合数对 $k$ 的余数，再对每个询问枚举所有合法 $(i,j)$ ：

cpp

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/**
 * 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-07-19 11:59
 * update_at: 2026-07-19 11:59
 */
#include <bits/stdc++.h>
using namespace std;

// brute.cpp：用 Pascal 递推直接算小范围组合数取模，再枚举询问范围。

const int MAXN = 105;

int t, k;
int comb_mod[MAXN][MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> t >> k;

    comb_mod[0][0] = 1 % k;
    for (int i = 1; i < MAXN; i++) {
        comb_mod[i][0] = comb_mod[i][i] = 1 % k;
        for (int j = 1; j < i; j++) {
            comb_mod[i][j] = (comb_mod[i - 1][j - 1] + comb_mod[i - 1][j]) % k;
        }
    }

    while (t--) {
        int n, m;
        cin >> n >> m;
        int answer = 0;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= min(i, m); j++) {
                if (comb_mod[i][j] == 0) {
                    answer++;
                }
            }
        }
        cout << answer << '\n';
    }

    return 0;
}

一组询问最多检查约 $O(nm)$ 个位置。若对 $10^4$ 组询问重复枚举，就无法通过完整数据。问题的关键是：所有询问使用同一个 $k$ ，可以把整张答案表预处理一次。

Pascal 递推只保留余数

组合数满足：

\binom{i}{j}=\binom{i-1}{j-1}+\binom{i-1}{j}.

题目只关心组合数能否被 $k$ 整除，所以不需要计算可能非常大的组合数，只需维护：

c_j=\binom{i}{j}\bmod k.

从第 $i-1$ 行更新到第 $i$ 行时，必须让 $j$ 从右向左遍历。这样读取 combination[j] 和 combination[j-1] 时，它们仍然都是上一行的值，不会被当前行提前覆盖。

样例 DP 表

这张表展示样例 $k=2$ 时，Pascal 递推得到的 $\binom{i}{j}\bmod 2$ ：

`i \ j`	`0`	`1`	`2`	`3`
`0`	`1`	-	-	-
`1`	`1`	`1`	-	-
`2`	`1`	`0`	`1`	-
`3`	`1`	`1`	`1`	`1`

行表示 $i$ ，列表示 $j$ ，单元格是对应组合数除以 $2$ 的余数。计算 $(2,1)$ 时，两个来源是上一行的 $(1,0)$ 与 $(1,1)$ ，所以得到 $(1+1)\bmod 2=0$ 。余数为 0 的位置就是可被 $k$ 整除的位置，因此样例矩形内只有 $(2,1)$ 被计数。

对可整除位置建立二维前缀和

定义：

bad[i][j]= \begin{cases} 1,&j\leqslant i\text{ 且 }\binom{i}{j}\bmod k=0,\\ 0,&\text{其它情况}. \end{cases}

再建立二维前缀和：

sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+bad[i][j].

询问 $(n,m)$ 对应矩形 $[0,n]\times[0,\min(n,m)]$ ，答案直接是 sum[n][min(n,m)]。虽然矩形中还包含 $j>i$ 的坐标，但这些位置的 bad 被定义为 0，不会造成误计。

原 main.py 已使用相同模型，但预处理仍包含约四百万次 Python 层二维前缀更新和多次对象访问，在评测限制下没有通过。C++ 使用连续的全局整型数组，并把 Pascal 余数压成一行，预处理开销和内存都更稳定。

正确性说明

Pascal 恒等式对所有合法 $i,j$ 成立，对等式两边取模后仍成立。因此从第 $0$ 行开始递推，combination[j] 正确保存当前 $\binom{i}{j}\bmod k$ 。

于是 bad[i][j]=1 当且仅当 $(i,j)$ 合法且 $k$ 整除 $\binom{i}{j}$ 。二维前缀和按照定义统计从 $(0,0)$ 到 $(n,m)$ 的所有标记；将 $m$ 截为 $\min(n,m)$ 后，这个矩形恰好覆盖题目要求的全部坐标，非法的 $j>i$ 位置贡献为零。因此每个询问答案正确。

代码

cpp

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/**
 * 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-07-19 11:59
 * update_at: 2026-07-19 11:59
 */
#include <bits/stdc++.h>
using namespace std;

const int LIMIT = 2000;

int test_count, divisor;
int combination[LIMIT + 1]; // 当前 Pascal 行的 C(i,j) mod k。
int prefix_bad[LIMIT + 1][LIMIT + 1];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> test_count >> divisor;

    combination[0] = 1 % divisor;
    for (int i = 0; i <= LIMIT; i++) {
        if (i > 0) {
            // 从右向左更新，避免覆盖本轮仍要使用的上一行状态。
            for (int j = i; j >= 1; j--) {
                combination[j] = (combination[j] + combination[j - 1]) % divisor;
            }
        }

        for (int j = 0; j <= LIMIT; j++) {
            int divisible = (j <= i && combination[j] == 0 ? 1 : 0);
            int up = (i > 0 ? prefix_bad[i - 1][j] : 0);
            int left = (j > 0 ? prefix_bad[i][j - 1] : 0);
            int diagonal = (i > 0 && j > 0 ? prefix_bad[i - 1][j - 1] : 0);
            prefix_bad[i][j] = up + left - diagonal + divisible;
        }
    }

    while (test_count--) {
        int n, m;
        cin >> n >> m;
        if (m > n) m = n;
        cout << prefix_bad[n][m] << '\n';
    }
    return 0;
}

复杂度

令上界 $N=2000$ 。

Pascal 递推和二维前缀和预处理时间为 $O(N^2)$ 。
每组询问只访问一个前缀和位置，时间为 $O(1)$ ；总时间复杂度为 $O(N^2+t)$ 。
二维前缀和占用 $O(N^2)$ 空间，滚动的组合数余数行占用 $O(N)$ 空间。
brute.cpp 每组询问直接枚举，最坏为 $O(tN^2)$ ，只用于小数据对拍。

总结

大量询问共享同一个 $k$ ，所以应把“计算组合数”和“统计询问范围”拆开预处理。Pascal 递推避免计算巨大组合数，二维前缀和把每次范围统计降为 $O(1)$ ；一维滚动更新还把组合数表从 $O(N^2)$ 压缩到 $O(N)$ 。

测试点	$n$	$m$	$k$	$t$
$1$	$\le3$	$\le3$	$=2$	$=1$
$2$	^	^	$=3$	$\le10^4$
$3$	$\le7$	$\le7$	$=4$	$=1$
$4$	^	^	$=5$	$\le10^4$
$5$	$\le10$	$\le10$	$=6$	$=1$
$6$	^	^	$=7$	$\le10^4$
$7$	$\le20$	$\le100$	$=8$	$=1$
$8$	^	^	$=9$	$\le10^4$
$9$	$\le25$	$\le2000$	$=10$	$=1$
$10$	^	^	$=11$	$\le10^4$
$11$	$\le60$	$\le20$	$=12$	$=1$
$12$	^	^	$=13$	$\le10^4$
$13$	$\le100$	$\le25$	$=14$	$=1$
$14$	^	^	$=15$	$\le10^4$
$15$	^	$\le60$	$=16$	$=1$
$16$	^	^	$=17$	$\le10^4$
$17$	$\le2000$	$\le100$	$=18$	$=1$
$18$	^	^	$=19$	$\le10^4$
$19$	^	$\le2000$	$=20$	$=1$
$20$	^	^	$=21$	$\le10^4$