P2822 [NOIP 2016 提高组] 组合数问题 · 习题解析

0题目原文（本地存了一份）

为什么要在这儿抄一份题面

原题在洛谷上（页头有链接）。别人的网站不归我们管，打不开、改版、题号调整都可能发生。所以每个解析页都把题面转录一份存在本地，跟着仓库一起进版本库。

转录自洛谷 P2822，日期见页头。两边不一致时信原站。

题目背景

NOIP2016 提高组 D2T1。

题目描述

组合数 C(n, m) 表示的是从 n 个物品中选出 m 个物品的方案数。举个例子，从 (1,2,3) 三个物品中选择两个物品可以有 (1,2), (1,3), (2,3) 这三种选择方法。根据组合数的定义，我们可以给出计算组合数 C(n, m) 的一般公式：

C(n, m) = n! / (m! · (n−m)!)

其中 n! = 1 × 2 × … × n；特别地，定义 0! = 1。

小葱想知道如果给定 n, m 和 k，对于所有的 0 ≤ i ≤ n，0 ≤ j ≤ min(i, m) 有多少对 (i, j) 满足 k 整除 C(i, j)。

输入格式

第一行有两个整数 t, k，其中 t 代表该测试点总共有多少组测试数据，k 的意义见问题描述。

接下来 t 行每行两个整数 n, m，其中 n, m 的意义见问题描述。

输出格式

共 t 行，每行一个整数代表所有的 0 ≤ i ≤ n，0 ≤ j ≤ min(i, m) 中有多少对 (i, j) 满足 k 整除 C(i, j)。

数据范围

对于全部的测试点，保证 0 ≤ n, m ≤ 2×10³，1 ≤ t ≤ 10⁴。

★ 子任务表里 k 从 2 一路取到 21（每两个测试点一个 k）；而 20 个测试点里有 10 个写着 t = 1，另外 10 个是 t ≤ 10⁴。

时限 1 秒，内存 500 MB（512000 KB）。

输入输出样例

输入

1 2
3 3

输出

样例 1：k = 2，问 n = m = 3。在所有可能的情况中，只有 C(2,1) = 2 一种是 2 的倍数。

输入

2 5
4 5
6 7

输出

0
7

样例 2：k = 5，两组询问 (4,5) 和 (6,7)。

1★★ 第一件事：把「k 整除 C(i,j)」换掉

★★★ 真值到不了 —— 而你根本不需要真值

C(2000, 1000) 有 600 位，任何整数类型都装不下。可题目问的不是 C(i,j) 是多少，只问它能不能被 k 整除。

⇒ 把本章第 3 步那份杨辉三角全程对 k 取模：

k 整除 C(i,j) ⟺ 取模之后那一格是 0。

一张 2001 × 2001 的表推完只要 200 万次加法，而每一格都是 [0, k) 里的小数。

⚠⚠ 而这道题恰恰不能用本章第 6 步那套「阶乘 + 逆元」 —— 它一口气踩了两个前提，下面第 ④ 步会把这件事跑出来看。

2第 ① 版：每次询问重推一遍三角 —— 稳拿 50 分

p2822Brute.cpp第 ① 版：每组询问重推三角再数 —— 参照物，稳拿 50 分

// 第 ① 版 / 参照物：每来一组询问，就把杨辉三角**重推一遍**再数
//
// 这是所有人真实的第一反应，而且它**稳拿 50 分** ——
// 题面那张子任务表里，20 个测试点有 **10 个写着 `t = 1`**：
// 只问一次的话，推一遍 2000 × 2000 的三角才 200 万次加法，本机几毫秒。
//
// ⚠ 另外 10 个点是 `t ≤ 10⁴` ⇒ 10⁴ × 4×10⁶ = **4×10¹⁰** 次，稳挂。
// ⇒ ★ 它是参照物，也是「暴力值多少分」的答案。
#include <bits/stdc++.h>
using namespace std;

const int N = 2000;
static int C[N + 1][N + 1];

int main() {
    int t, k;
    if (scanf("%d %d", &t, &k) != 2) return 0;
    while (t--) {
        int n, m;
        if (scanf("%d %d", &n, &m) != 2) return 0;
        for (int i = 0; i <= n; i++) {
            C[i][0] = 1 % k;
            for (int j = 1; j <= i; j++) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % k;
        }
        long long ans = 0;
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= i && j <= m; j++)
                if (C[i][j] == 0) ans++;
        printf("%lld\n", ans);
    }
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★ 那 50 分是题面自己给的：20 个测试点里 10 个写着 t = 1

只问一次的话，推一遍 2000 × 2000 的三角才 200 万次加法，本机几毫秒 —— 「暴力值多少分」是「暴力 × 那道题分档」的属性的又一次，而这一次分档写在子任务表里，不在「对于 X% 的数据」那几行里。

⚠ 另外 10 个点是 t ≤ 10⁴ ⇒ 10⁴ × 4×10⁶ = 2×10¹⁰ 次，稳挂。

3⚠ 第 ② 版：三角只推一次了 —— 可它一分钱都没多拿

p2822Pre.cpp⚠ 第 ② 版：三角预处理一次，可每次询问还是扫一遍 —— 还是 50 分

★★ 「把和询问无关的部分摘出来」是对的一步，但它不是瓶颈

	次数
推一次三角	2 001 000（只做一次）
每次询问扫半张表	2 002 000 ⇒ `t = 10⁴` 时 2×10¹⁰

⇒ 两版分数完全一样（都是 50 分）。可这一步非走不可 —— 摘掉预处理之后，剩下的形状才看得清： 同一张表被问一万次，而每次问的都是「左上角一块里有几个 0」 ⇒ 这正是第 6 章二维前缀和的形状。

★ 单次扫描实测 1.36 ms ⇒ 一万次外推 13 560 ms（时限 1000）；加上前缀和之后，一万次询问一共 5.9 ms，余量 170 倍。

p2822.cpp★ 正解：三角边推边取模 + 二维前缀和 —— AC

// P2822 组合数问题 —— 正解：杨辉三角**边推边对 k 取模** ＋ 二维前缀和
//
// 问的是：0 ≤ i ≤ n、0 ≤ j ≤ min(i, m) 里，有多少对 (i, j) 满足 k | C(i, j)。
//
// ★ 两件事拼起来就完了：
//   ① [本章第 3 步](/ch/43-combinatorics/)那份杨辉三角，全程 **% k** ——
//      于是「k 整除 C(i,j)」就等价于「表里那一格是 0」，**根本不用算出 C(i,j) 的真值**
//      （真值到不了：C(2000,1000) 有 600 位）。
//   ② 一层[第 6 章](/ch/06-prefix-diff/)的二维前缀和，把每次询问压成 O(1)。
//
// ⚠⚠ 这道题**恰恰不能用逆元那一套**（见 p2822Inv.cpp）：
//   `k` 只保证 2 ≤ k ≤ 21，**不保证是质数**；就算碰巧是质数，i 也远大于 k
//   ⇒ 本章第 6 步那个「p > n」的前提也不成立。
//   ⇒ 杨辉三角在这里不是「暴力」，它是**唯一走得通的那条路**。
//
// ⚠ `k` 写在**第一行**，全部 t 组询问共用一个 —— 所以预处理只做一次（见 p2822Fmt.cpp）。
#include <bits/stdc++.h>
using namespace std;

const int N = 2000;
static int C[N + 1][N + 1];       // 杨辉三角，全程 % k
static int s[N + 1][N + 1];       // 二维前缀和：s[i][j] = 前 i 行、前 j 列里有几个 0

int main() {
    int t, k;
    if (scanf("%d %d", &t, &k) != 2) return 0;

    for (int i = 0; i <= N; i++) {
        C[i][0] = 1 % k;
        for (int j = 1; j <= i; j++) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % k;
    }
    for (int i = 0; i <= N; i++)
        for (int j = 0; j <= N; j++) {
            int cell = (j <= i && C[i][j] == 0) ? 1 : 0;     // ★ j ≤ i 这一半不能少
            s[i][j] = cell
                    + (i ? s[i - 1][j] : 0)
                    + (j ? s[i][j - 1] : 0)
                    - (i && j ? s[i - 1][j - 1] : 0);
        }

    while (t--) {
        int n, m;
        if (scanf("%d %d", &n, &m) != 2) return 0;
        printf("%d\n", s[n][m]);
    }
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

4✗ 错法一：把本章第 6 步那套模板搬过来 —— 它踩了两个前提

p2822Inv.cpp✗ 阶乘 + 逆元：k 不保证是质数，而且 i 远大于 k

★★★ 两个前提各挡一半，而这道题两个都不满足

模数得是质数 —— 逆元靠费马小定理。而这道题的 k 只保证 2 ≤ k ≤ 21， 4 / 6 / 8 / 9 / 10 / 12 / … 全在里面。 ⚠ qpow(x, k−2) 在 k 不是质数时算出来是个没有意义的数，而它不报错、不崩 —— 程序只是安静地在算一个和组合数无关的量。
还得 p > n —— 就算 k 碰巧是质数（2/3/5/7/…），这里 i 一路到 2000 ≫ k ⇒ i! 里含着因子 k ⇒ fac[i] ≡ 0 ⇒ 它会把几乎每一格都判成 0。

⇒ 它错得很彻底：样例 1 打出 7（正解 1），样例 2 打出 0 / 13（正解 0 / 7）。

★★ 和上一道 P3807 连起来看，这一章的两道题各拆了那套模板的一个前提： P3807 拆的是 p > n（p 仍是质数），这道题两个一起拆。 ⇒ 记一个模板的时候，把它的前提一起记下来 —— 前提失效的那一天，模板不会报错。

5✗ 错法二：前缀和忘了「只数三角形里面的」

p2822NoTri.cpp✗ 前缀和铺满了整张方表 —— j > i 那半边也被数了进去

★★ 它多数的那一片，恰好是「C(i,j) = 0」的那一片 —— 而 k | 0 确实成立

题面写的是 0 ≤ j ≤ min(i, m) —— j 不能超过 i。可写前缀和时最顺手的是「把整张 2001 × 2001 铺满」，而 j > i 那半边的 C[i][j] 从来没被赋过值，静态数组里全是 0。

★ 所以这不是「读到了脏数据」—— 那半边的组合数真的是 0，而 k | 0 在数学上确实成立。它干的事是：把一个题面没问的、但确实为真的东西也数了进去。 ⇒ 答案恒 ≥ 正解（样例 1：7 vs 1；样例 2：15 / 35 vs 0 / 7）。

⇒ 「说清楚一个 bug 算了什么，比说它错了有用得多」的又一次：说清之后，「它只在 m ≥ 1 时才差得出来」「它恒偏大」都是白送的推论。

6✗ 错法三：把 k 当成「每组一个」读了

p2822Fmt.cpp✗ 和算法无关的一条：输入格式读错，从第一组就错位

⚠ 上一道题的模数写在每一组里，这一道写在第一行 —— 而两道题就挨着

P3807 的输入是「每组 n m p」，这道题是「第一行 t k，之后每行 n m」。连着做两道，手就会自己写成「每组读三个数」⇒ 从第一组起整个错位。

⇒ 「同一张题单里两道题的输入格式相反」的又一次 —— 而这一次它们前后脚。 ★ 好在这一条样例一测就死（样例 1 打出 0）。

7★★★ 一个反直觉的精确的 0：不取模，居然也可能全对

p2822Raw.cpp✗ 三角不取模，最后判整除 —— 而 k 是 2 的幂时它一格都不会错

★★★ 模 2⁶⁴ 绕回，只丢掉 2⁶⁴ 的整数倍 —— 而 2 的幂整除 2⁶⁴

「三角不取模、最后判 C % k == 0」听着更诚实，可 C(68, 34) 就已经越过 2⁶⁴ 了（度量程序从第 0 行数上去：第 68 行是第一个）。

按理说，之后每一格都是「真值模 2⁶⁴」，判整除当然会乱。 ★★★ 可 k 是 2 的幂时它一格都不会错 —— 整张 2001 × 2001 的表逐格比：

`k`	判断不同的格子	`k`	判断不同的格子
2	★ 0	3	1 243 833
4	★ 0	5	1 394 668
8	★ 0	6	1 154 471
16	★ 0	7	1 400 687

证明一行：绕回丢掉的是 2⁶⁴ 的整数倍，而 2 | 2⁶⁴、4 | 2⁶⁴、8 | 2⁶⁴、16 | 2⁶⁴ ⇒ 「能不能被 2 的幂整除」这件事在绕回之后一点没变。

★ 而右边那一列就是这四个 0 的自检：同一段代码、同一张表，只换一个 k，当场一百多万格不一样 ⇒ 它绝不是「没在跑」。

⇒ 第 40 章 P2651 那条（a₂ 是 2 的幂时，模 2⁶⁴ 绕回照样保持整除） 换了一道题又拦了一次路 —— ⚠ 而子任务表里 k = 2/4/8/16 占了 4 个 k 值、8 个测试点。

8★ 生成器：四个档，触发和抓获十二格全部一个不差

p2822Gen.cpp（四档）生成器：顺手写的 / 照题面 / ⚠ k 只取 2 的幂 / ⚠ k 只取含奇因子的

★★ 四个档 × 五个版本（每档 300 轮）

档位	✗ 不取模	✗ 阶乘+逆元	✗ 没限制 j ≤ i	✗ 输入格式
0 顺手写的（`n,m ≤ 30`）	★ 0（触发 0）	275	297	295
1 照题面（`n,m ≤ 2000`、`k ∈ [2,21]`）	244 ≡ 244	299	300	299
⚠ 2 `k` 只取 2 的幂	★ 0 ≡ 0	300	300	299
⚠ 3 `k` 只取含奇因子的	298 ≡ 298	300	300	300

★★ 「不取模」那一列四格全是「触发 ≡ 抓获」，而触发条件是两层且缺一不可： ① k 含奇因子，② 询问真的问到了第 68 行以后。 ⇒ 档 0 那个 0 是「行数不够」，档 2 那个 0 是「k 的形状」—— 两个 0 长得一模一样，原因完全不同，而两个都能证。

★ 最后一列同样值钱：两个暴力（每次重推 / 预处理一次）在 1200 轮里一次都没和正解不一致 ⇒ 它们不是「错」，是「对但跑不完」。样例和对拍对这种情况完全无能为力 —— 只能数次数。

9★ 哪一版就已经能过了

p2822Count.cpp本页所有数字的出处

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

// P2822 的度量程序：./p2822Count csv        （本页的数字都出自它）
//
//   line  : ★ 三角不取模的话，**第几行**第一次越过 2⁶⁴。
//   pow2  : ★★★ 「k 是 2 的幂 ⇒ 不取模也全对」—— 把整张 2001×2001 的表逐格比一遍，
//           k ∈ {2,4,8,16} 和 k = 3/5/6/7 各是多少格不一样（这就是那个精确的 0 的证明 ＋ 自检）。
//   trig  : ★ 四个档里 Raw 的触发条件 / 真被抓各几轮。
//   cost  : ★ 三种写法的次数账 ＋ 顶格秒表（t = 10⁴、n = m = 2000）。
//
// ⚠ 这里**复刻**了 p2822Gen.cpp 的档位逻辑（同一个 mt19937、同一个种子公式）。
// ⚠ 秒表用 steady_clock 在进程内量，3 次取中位数
//   （[第 12 章 P1923 那一跤](/sol/p1923/)：秒表断言的主语是余量，不是量级）。
#include <bits/stdc++.h>
#include <chrono>
using namespace std;
using namespace std::chrono;
typedef long long ll;
typedef unsigned long long ull;

static double med3(double a, double b, double c) { return max(min(a, b), min(max(a, b), c)); }

const int N = 2000;
static int Cmod[N + 1][N + 1];
static ull Craw[N + 1][N + 1];
static char ovf[N + 1][N + 1];          // 这一格的真值有没有越过 2⁶⁴
static int sMod[N + 1][N + 1];

static void buildMod(int k) {
    for (int i = 0; i <= N; i++) {
        Cmod[i][0] = 1 % k;
        for (int j = 1; j <= i; j++) Cmod[i][j] = (Cmod[i - 1][j - 1] + Cmod[i - 1][j]) % k;
    }
    for (int i = 0; i <= N; i++)
        for (int j = 0; j <= N; j++) {
            int cell = (j <= i && Cmod[i][j] == 0) ? 1 : 0;
            sMod[i][j] = cell + (i ? sMod[i - 1][j] : 0) + (j ? sMod[i][j - 1] : 0)
                       - (i && j ? sMod[i - 1][j - 1] : 0);
        }
}

/** 复刻 p2822Gen.cpp */
static void gen(unsigned seed, int mode, int& k, vector<pair<int, int>>& qs) {
    mt19937 rng(seed * 1000003u + 20260903u);
    const int POW2[4] = {2, 4, 8, 16};
    const int ODDF[13] = {3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 18, 21};
    if (mode == 2) { unsigned r = rng() % 4u; k = POW2[r]; }
    else if (mode == 3) { unsigned r = rng() % 13u; k = ODDF[r]; }
    else { unsigned r = rng() % 20u; k = 2 + (int)r; }
    int nmMax = mode == 0 ? 30 : 2000;
    int t = 1 + (int)(rng() % 3u);
    qs.clear();
    for (int i = 0; i < t; i++) {
        unsigned r1 = rng() % (unsigned)(nmMax + 1), r2 = rng() % (unsigned)(nmMax + 1);
        qs.push_back({(int)r1, (int)r2});
    }
}

int main(int argc, char** argv) {
    bool csv = (argc > 1 && string(argv[1]) == "csv");

    /* ① 三角不取模：第几行第一次越过 2⁶⁴ */
    int firstOvf = -1;
    for (int i = 0; i <= N; i++) {
        Craw[i][0] = 1; ovf[i][0] = 0;
        for (int j = 1; j <= i; j++) {
            ull a = Craw[i - 1][j - 1], b = Craw[i - 1][j];
            Craw[i][j] = a + b;
            ovf[i][j] = (ovf[i - 1][j - 1] || ovf[i - 1][j] || Craw[i][j] < a) ? 1 : 0;
            if (ovf[i][j] && firstOvf < 0) firstOvf = i;
        }
    }

    /* ② 「k 是 2 的幂 ⇒ 不取模也全对」：整张表逐格比 */
    int diffPow2[4], diffOdd[4];
    const int POW2[4] = {2, 4, 8, 16}, ODD[4] = {3, 5, 6, 7};
    for (int t = 0; t < 4; t++) {
        for (int which = 0; which < 2; which++) {
            int k = which ? ODD[t] : POW2[t];
            buildMod(k);
            int diff = 0;
            for (int i = 0; i <= N; i++)
                for (int j = 0; j <= i; j++) {
                    bool a = (Cmod[i][j] == 0);
                    bool b = (Craw[i][j] % (ull)k == 0);
                    if (a != b) diff++;
                }
            if (which) diffOdd[t] = diff; else diffPow2[t] = diff;
        }
    }

    /* ③ 四个档：Raw 的触发条件 / 真被抓 */
    int trigRaw[4] = {0, 0, 0, 0}, badRaw[4] = {0, 0, 0, 0};
    for (int mode = 0; mode < 4; mode++) {
        int k; vector<pair<int, int>> qs;
        for (int s = 1; s <= 300; s++) {
            gen((unsigned)s, mode, k, qs);
            bool oddK = false;
            { int kk = k; while (kk % 2 == 0) kk /= 2; oddK = (kk > 1); }
            int maxN = 0;
            for (auto& q : qs) maxN = max(maxN, q.first);
            if (oddK && maxN >= firstOvf) trigRaw[mode]++;   // 第一层：k 含奇因子 且 问到了溢出的行
            buildMod(k);
            bool bad = false;
            for (auto& q : qs) {
                int n = q.first, m = q.second;
                int truth = sMod[n][m];
                int raw = 0;
                for (int i = 0; i <= n; i++)
                    for (int j = 0; j <= i && j <= m; j++)
                        if (Craw[i][j] % (ull)k == 0) raw++;
                if (raw != truth) bad = true;
            }
            if (bad) badRaw[mode]++;
        }
    }

    /* ④ 次数账 ＋ 顶格秒表 */
    const ll TT = 10000;
    ll opsBuild = (ll)N * (N + 1) / 2;                 // 推一次三角
    ll opsPerQuery = (ll)(N + 1) * (N + 1) / 2;        // 一次询问扫半张表
    double msFinal;
    {
        double t[3];
        for (int r = 0; r < 3; r++) {
            auto t0 = steady_clock::now();
            buildMod(7);
            volatile ll sink = 0;
            for (ll q = 0; q < TT; q++) sink += sMod[N][N];
            t[r] = duration<double, milli>(steady_clock::now() - t0).count();
        }
        msFinal = med3(t[0], t[1], t[2]);
    }
    double msOneScan;
    {
        buildMod(7);
        double t[3];
        for (int r = 0; r < 3; r++) {
            auto t0 = steady_clock::now();
            volatile ll cnt = 0;
            for (int i = 0; i <= N; i++)
                for (int j = 0; j <= i; j++) if (Cmod[i][j] == 0) cnt++;
            t[r] = duration<double, milli>(steady_clock::now() - t0).count();
        }
        msOneScan = med3(t[0], t[1], t[2]);
    }

    if (csv) {
        printf("firstOvf,%d\n", firstOvf);
        for (int i = 0; i < 4; i++) printf("diffPow2_%d,%d\n", POW2[i], diffPow2[i]);
        for (int i = 0; i < 4; i++) printf("diffOdd_%d,%d\n", ODD[i], diffOdd[i]);
        for (int i = 0; i < 4; i++) printf("trigRaw%d,%d\n", i, trigRaw[i]);
        for (int i = 0; i < 4; i++) printf("badRaw%d,%d\n", i, badRaw[i]);
        printf("opsBuild,%lld\n", opsBuild);
        printf("opsPerQuery,%lld\n", opsPerQuery);
        printf("opsBruteTop,%.3g\n", (double)opsPerQuery * (double)TT);
        printf("msFinal,%.1f\n", msFinal);
        printf("msOneScan,%.2f\n", msOneScan);
        printf("msScanTopProj,%.0f\n", msOneScan * (double)TT);
        return 0;
    }

    printf("① 三角不取模：第 **%d** 行第一次越过 2⁶⁴（C(%d, %d) 就装不下了）\n",
           firstOvf, firstOvf, firstOvf / 2);
    printf("\n② 「k 是 2 的幂 ⇒ 不取模也全对」——整张 2001×2001 的表逐格比\n");
    for (int i = 0; i < 4; i++)
        printf("   k = %-2d（2 的幂）判断不同的格子：**%d**        k = %-2d（含奇因子）：%d\n",
               POW2[i], diffPow2[i], ODD[i], diffOdd[i]);
    printf("   ⇒ ★★ 左边四个 0 是**能证的**：模 2⁶⁴ 绕回只丢掉 2⁶⁴ 的整数倍，而 2 的幂整除 2⁶⁴\n");
    printf("   ⇒ ★ 右边那一列就是这四个 0 的自检（同一段代码，换个 k 当场几十万格不一样）\n");

    const char* NAME[4] = {"顺手写的（n,m ≤ 30）", "照题面（n,m ≤ 2000、k ∈ [2,21]）",
                           "⚠ k 只取 2 的幂", "⚠ k 只取含奇因子的"};
    printf("\n③ 四个档各 300 轮：不取模那一版\n");
    for (int i = 0; i < 4; i++)
        printf("   档 %d %-34s 触发（k 含奇因子 且 问到第 %d 行以后）%3d 轮 ／ 真被抓 %3d 轮\n",
               i, NAME[i], firstOvf, trigRaw[i], badRaw[i]);

    printf("\n④ 次数账（顶格 t = 10⁴、n = m = 2000；独占实测，3 次取中位数；时限 1000 ms）\n");
    printf("   推一次三角              %9lld 次\n", opsBuild);
    printf("   每次询问扫一遍          %9lld 次 ⇒ 一万次询问 %.3g 次（单次实测 %.2f ms ⇒ 外推 %.0f ms）\n",
           opsPerQuery, (double)opsPerQuery * (double)TT, msOneScan, msOneScan * (double)TT);
    printf("   ★ 三角 + 二维前缀和     一万次询问共 **%.1f ms** ⇒ 余量 %.0f 倍\n", msFinal, 1000.0 / msFinal);
    return 0;
}

点一下即可编辑

输出

点「运行 ▶」看结果

★ 只有第 ③ 版能拿满分 —— 而两个暴力都值 50 分，三个错法各死在不同的地方

版本	顶格代价	交上去
① 每次重推三角	2×10¹⁰ 次	50 分（`t = 1` 的那 10 个点）
② 预处理一次，仍逐次扫	2×10¹⁰ 次	50 分（一分没多拿）
★ ③ 三角 + 二维前缀和	一万次询问共 5.9 ms	★ AC，余量 170 倍
✗ 阶乘 + 逆元	—	0 分（两个前提都不成立）
✗ 没限制 `j ≤ i`	—	0 分（多数了「`C = 0`」那一片）
✗ 不取模	—	★ 8 个测试点照样对（`k` = 2/4/8/16 那几个）

⇒ 这道题把这一章的两句话摆在一起了： 「取模之下不能除」的另一面是「取模之下加法照样对」 —— 组合数的递推只有加法，所以杨辉三角在任何模数下都成立；而阶乘 + 逆元那套要除法，于是它对模数挑三拣四。 ★ 哪条路能走，是模数说了算的。

洛谷 P2822 [NOIP 2016 提高组] 组合数问题

0题目原文（本地存了一份）

输入

输出

输入

输出

1★★ 第一件事：把「k 整除 C(i,j)」换掉

2第 ① 版：每次询问重推一遍三角 —— 稳拿 50 分

3⚠ 第 ② 版：三角只推一次了 —— 可它一分钱都没多拿

4✗ 错法一：把本章第 6 步那套模板搬过来 —— 它踩了两个前提

5✗ 错法二：前缀和忘了「只数三角形里面的」

6✗ 错法三：把 k 当成「每组一个」读了

7★★★ 一个反直觉的精确的 0：不取模，居然也可能全对

8★ 生成器：四个档，触发和抓获十二格全部一个不差

9★ 哪一版就已经能过了