先给结论：2016 年青岛站的 H 题“Great Cells”，是一道非常典型的“数学推导 + 思维”题。代码量不大，核心推导链却很长，赛场上容易卡住。我第一次补这题时，第一反应是往容斥、状压、组合 DP 方向想，结果绕了不少弯路。实际拆开看，这题只靠两把钥匙就能解开：期望线性性，以及自然数幂和的拉格朗日插值。

题目本身是这样一个场景：一个 n × m 的网格，每个格子独立填 1 到 K 的整数。定义一个“好格子”（Great Cell）：该格子的数字要严格大于它所在行、所在列的所有其他格子。现在要求把所有可能的填数方案全部列出来，统计每个方案里好格子的数量，最后求和。这个“所有方案的好格子数量总和”，就是答案。

这个题适合谁看？准备 ICPC / CCPC 的选手，或者正在刷 Gym 题单、想提升组合计数思维的人，都可以把这道题当成一个很好的“思维转折”训练。它不考高级数据结构，不考复杂算法，考的是你遇到计数问题时，能不能快速把问题转成期望问题，再认出藏在里面的幂和多项式。下面我完整拆一遍推导过程、代码实现和踩坑细节。

1. 题目到底在问什么，为什么不能硬枚举

1.1 形式化描述与关键区别

先把题面重新描述一遍，确保每个细节都对齐。给定 n、m、K，总共有 K^(n×m) 种填数方案。对某一种方案，定义一个格子为 Great Cell，当且仅当它格子里的值，严格大于与它同行、同列的每一个格子里的值。注意是“同行同列的其他格子”，也就是和它共享行或共享列的所有格子，一共有 n + m - 2 个约束格子。

题目要求的最终答案不是“存在好格子的方案数”，也不是“恰好有 g 个好格子的方案数”，而是所有方案中好格子出现次数的总和。用公式写，就是令 cnt(S) 表示方案 S 中好格子的数量，求：

sum over所有方案 S cnt(S)

这个区别很关键。如果题目问的是“有多少种方案至少有一个好格子”，那大概率要容斥；如果问的是“恰好 g 个”，那可能要考虑行列排列和数值约束的结构。但这里问的是总和，意味着我们有机会用期望线性性把问题拆开，不需要关心方案之间好格子的依赖关系。

1.2 为什么暴力枚举不可行

一个很自然的想法是直接枚举网格状态，但 K^(n×m) 这个量级太可怕了。就算 K 很小，比如 K=2，n=m=3，也有 2^9=512 种方案，勉强能枚举；但题目里 K 可以到 1e9，n、m 也可以到 2000 级别，总方案数根本不可能显式枚举。

按好格子数量 g 分类似乎有点希望，但要同时处理“行/列上不能有另一个好格子”“数值要满足严格大于”这些约束，需要讨论的排列结构非常复杂，而且 K 很大的时候数值约束也不好处理。这条路线在赛场上基本走不通。

正确的角度是：把“所有方案中好格子数量总和”看成“随机选择一种填数方案时，好格子数量的期望，再乘以总方案数”。也就是：

答案 = 总方案数 × E[好格子数量]

一旦想到期望，下一步就顺了：期望是线性算子，好格子总数量等于每个格子作为好格子的指示变量之和，所以期望等于每个格子是好格子的概率相加。而且，这里不需要这些事件彼此独立。这是线性性最“反直觉”也最好用的地方。

2. 公式推导：从单格概率到最终和式

2.1 固定一个格子，算它是好格子的概率

随便取一个格子，比如左上角 (1,1)。因为填数规则对每个格子完全对称，所以每个格子是好格子的概率都相同。下面固定这个格子算概率。

假设这个格子的值为 x。它要成为好格子，需要满足：与它同行同列的所有其他格子，值都必须严格小于 x。这里有个非常重要的细节：同行同列一共有多少个格子？

如果网格是 n 行 m 列，固定一个格子后，同一行有 m - 1 个其他格子，同一列有 n - 1 个其他格子，两者不重叠，因为固定格子本身被排除在外。所以总共 n + m - 2 个约束格子。这些格子各自独立取值，每个都必须在 [1, x-1] 中选择，方案数是 (x-1)^(n+m-2)。

剩下还有多少个格子不受约束？总格子数是 n×m，减去固定格子本身 1 个，再减去刚才的 n + m - 2 个约束格子，剩下：

n×m - 1 - (n + m - 2) = (n-1)(m-1)

这些格子可以自由填 1 到 K，方案数是 K^((n-1)(m-1))。

固定格子的值可以是 1 到 K 中的任意一个，所以“固定格子是好格子”这一事件包含的方案数为：

sum_{x=1}^{K} (x-1)^(n+m-2) × K^((n-1)(m-1))

总方案数是 K^(n×m)，所以固定格子是好格子的概率为：

P = [ sum_{x=1}^{K} (x-1)^(n+m-2) × K^((n-1)(m-1)) ] / K^(n×m)

将分母拆开：K^(n×m) = K^(n+m-1) × K^((n-1)(m-1))，因为 n+m-1 + (n-1)(m-1) = nm。于是上下约掉 K^((n-1)(m-1))，得到：

P = sum_{x=1}^{K} (x-1)^(n+m-2) / K^(n+m-1)

这个形式很干净。后面求总答案时，只需要再乘回总方案数。

2.2 汇总出最终公式

网格里一共有 n×m 个格子，每个格子是好格子的概率都是 P，所以：

E[好格子数量] = n×m × P

答案 = K^(n×m) × n×m × P

代入 P 的表达式，约分后得到：

答案 = n×m × K^((n-1)(m-1)) × sum_{x=1}^{K} (x-1)^(n+m-2)

令 i = x - 1，那么 i 从 0 取到 K - 1，最终公式：

答案 = n×m × K^((n-1)(m-1)) × sum_{i=0}^{K-1} i^(n+m-2)

到这一步，原问题已经变成了一个纯粹的数学问题：计算 sum_{i=0}^{K-1} i^p，其中 p = n + m - 2。

这里再补充一个有趣的观察：两个好格子不可能在同一行或同一列。因为如果同一行有两个好格子 A 和 B，那么 A 是好格子要求 A 的值大于 B 的值，B 是好格子又要求 B 的值大于 A 的值，矛盾，列同理。所以好格子只能分布在行列互不相同的位置。这个观察在算概率时不是必需的，但能帮助理解为什么用“单格概率 × 格子数”不会重复计算——线性性本身已经把重合的情况都处理好了。

2.3 代入小数据验证公式对不对

公式推出来之后，强烈建议先拿小数据手算一遍，确认没有推错方向。

例 1：n=1，m=2，K=2。总共有 2^2=4 种方案：

• (1,1)：第二个格子值为 1，与第一个格子相等，没有好格子；
• (1,2)：第二个格子值为 2，严格大于第一个格子的 1，所以它是好格子，数量 1；
• (2,1)：第一个格子值为 2，是好格子，数量 1；
• (2,2)：两个格子都为 2，没有严格大于关系，数量 0。

总和是 2。代入公式：n×m=2，K^((n-1)(m-1))=2^0=1，sum_{i=0}^{1} i^(1+2-2)=0^1+1^1=1，答案是 2。一致。

例 2：n=2，m=2，K=2。总共 2^4=16 种方案。固定一个格子，值为 2 且同行同列两个格子都为 1 时，它才是好格子，概率为 (1/2)×(1/2)^2=1/8。期望好格子数为 4×1/8=1/2。总答案=16×1/2=8。代入公式：4×2^(1×1)×(0^2+1^2)=4×2×1=8。一致。

两个例子都对，说明公式大概率没问题。接下来真正的工作重心就落在怎么快速求 sum_{i=0}^{K-1} i^p。

3. 自然数幂和：从暴力到拉格朗日插值

3.1 什么时候可以直接暴力累加

如果 K 很小，比如 K ≤ 2000 或者 K ≤ 10^5，直接 for 循环加快速幂完全可行。复杂度是 O(K log p)，在 K 不大的时候能轻松通过。

但本题的 K 可以到 1e9，p = n + m - 2 最大可以到 4000 左右。如果直接循环到 1e9，每次快速幂 log p 大约 12 次乘法，总操作数在 10^10 级别，必然超时。所以必须找数学方法。

这里的“数学方法”不是去背伯努利数公式，而是用一个更通用的结论：自然数幂和是一个多项式。具体来说，sum_{i=0}^{k} i^p 是关于 k 的 p+1 次多项式。比如：

• sum_{i=0}^{k} i = k(k+1)/2，是 2 次多项式；
• sum_{i=0}^{k} i^2 = k(k+1)(2k+1)/6，是 3 次多项式；
• 一般地，F(k) = sum_{i=0}^{k} i^p 是 p+1 次多项式。

这个结论的严格证明可以用有限差分或者伯努利多项式，但竞赛里记住结论就行。既然 F(k) 是 d = p+1 次多项式，那么只要知道 d+1 = p+2 个点上的函数值，就能唯一确定这个多项式，进而求出任意 k 处的值。

这正是拉格朗日插值的用武之地。我们不需要真的把多项式系数解出来，只需要在 k = K-1 处直接插值求值。

3.2 为什么可以用拉格朗日插值

拉格朗日插值的基本思想是：给定 d+1 个节点 (x_0, y_0), (x_1, y_1), ..., (x_d, y_d)，可以构造一个 d 次多项式，满足这些点的取值，并且在其他点上有定义。

对于本题，我们选取节点 x_j = j（j = 0, 1, ..., d），对应的 y_j = F(j) = sum_{i=0}^{j} i^p。这里 d = p+1，所以一共有 p+2 个节点。这些 y_j 值可以暴力算：从 0 到 d，每次用快速幂算 j^p，再累加。因为 d 不超过 4000，这部分复杂度完全可以接受。

拉格朗日插值公式是：

F(k) = sum_{j=0}^{d} y_j × prod_{t≠j} (k - x_t) / (x_j - x_t)

直接按这个公式做，每次求分母和分子都是 O(d)，总复杂度 O(d^2)。d=4000 时是 1.6×10^7，其实也能跑，但没必要。利用“节点是连续整数”这一特殊性质，可以把复杂度降到 O(d)。

3.3 连续整点节点的优化技巧：阶乘与前后缀积

因为 x_t = t，所以分母可以显式化简。对固定的 j：

prod_{t=0, t≠j}^{d} (j - t) = [prod_{t=0}^{j-1} (j - t)] × [prod_{t=j+1}^{d} (j - t)]

前半部分是 j × (j-1) × ... × 1 = j!。后半部分是 (-1) × (-2) × ... × (j-d) ？写成：

(j - (j+1)) × (j - (j+2)) × ... × (j - d) = (-1) × (-2) × ... × (j-d)

一共 d-j 项，每项都是负数，所以提取 (-1)^(d-j)，剩下的绝对值是 (d-j)!。因此：

分母 = j! × (-1)^(d-j) × (d-j)!

这个结果可以直接预处理阶乘和逆元，O(1) 得到分母的倒数。

分子部分 prod_{t≠j} (k - t)，如果对每个 j 单独算还是 O(d) 总 O(d^2)。这里可以用前缀积和后缀积优化：

定义 pre[j] = prod_{t=0}^{j} (k - t)，suf[j] = prod_{t=j}^{d} (k - t)。

那么排除 t=j 的乘积就是 pre[j-1] × suf[j+1]，前后各乘一遍即可，O(1) 得到分子。

把分子和分母拼起来，再处理符号 (-1)^(d-j)，就能在 O(d) 时间内完成插值。

有一个注意点：如果 k 恰好落在某个节点上，即 K-1 在 0 到 d 之间，直接用 y_{K-1} 返回就行，不需要插值。原因是插值公式里会出现 (k-j)=0 导致分子变 0，虽然最后结果会因为 y_j 恰好等于目标值而不出错，但实现时特判更干净。

3.4 边界情况：n=m=1 时 p=0 的问题

这题最容易被忽视的边界是 n=m=1。此时网格只有一个格子，这个格子没有同行同列的其他格子，“严格大于所有同行同列格子”的条件为空真，所以它一定是好格子。总共有 K 种填法，答案显然是 K。

带入公式：n×m=1，K^((n-1)(m-1))=K^0=1，p=n+m-2=0，于是需要计算 sum_{i=0}^{K-1} i^0。问题来了：i=0 时 0^0 在数学上通常约定为 1，因为每个格子都是好格子。但如果程序里直接用 pow_mod(0, 0)，不同实现可能返回 0 或 1，容易出错。

稳妥的做法是在实现自然数幂和时单独特判 p==0，直接返回 K % MOD。这样既避免了 0^0 的歧义，也让代码逻辑更清晰。

4. 代码落地：从公式到 AC

4.1 完整 C++17 实现

下面这份代码是完整可提交的版本。核心函数 sum_pow(k, p) 计算 sum_{i=0}^{k} i^p mod MOD，其中 k 可能很大，p 最大 4000 左右。主函数里预处理节点值、阶乘、逆元，最后用拉格朗日插值求答案。

#include <bits/stdc++.h> using namespace std; using ll = long long; const ll MOD = 1000000007LL; ll mod_pow(ll a, ll e) { ll r = 1; while (e > 0) { if (e & 1) r = r * a % MOD; a = a * a % MOD; e >>= 1; } return r; } // 返回 sum_{i=0}^{k} i^p mod MOD // 要求 p >= 1；p=0 时在外部特判 ll sum_pow(ll k, int p) { int d = p + 1; // F(k) 是 p+1 次多项式，需要 d+1 个点 vector<ll> y(d + 1), fact(d + 1), invFact(d + 1); // 计算节点 0..d 上的前缀和值 y[0] = 0; for (int i = 1; i <= d; ++i) { y[i] = (y[i - 1] + mod_pow(i, p)) % MOD; } if (k <= d) return y[(int)k]; // 预处理 0..d 的阶乘与逆元 fact[0] = 1; for (int i = 1; i <= d; ++i) fact[i] = fact[i - 1] * i % MOD; invFact[d] = mod_pow(fact[d], MOD - 2); for (int i = d; i >= 1; --i) invFact[i - 1] = invFact[i] * i % MOD; // 拉格朗日插值：节点 x_i = i // 分子 = prod_{t != j} (k - t) // 用 pre 和 suf 快速求 vector<ll> pre(d + 2), suf(d + 2); pre[0] = 1; for (int i = 0; i <= d; ++i) { pre[i + 1] = pre[i] * ((k - i) % MOD + MOD) % MOD; } suf[d + 1] = 1; for (int i = d; i >= 0; --i) { suf[i] = suf[i + 1] * ((k - i) % MOD + MOD) % MOD; } ll ans = 0; for (int j = 0; j <= d; ++j) { ll num = pre[j] * suf[j + 1] % MOD; ll den = invFact[j] * invFact[d - j] % MOD; ll term = y[j] * num % MOD * den % MOD; if ((d - j) & 1) { ans = (ans - term + MOD) % MOD; } else { ans = (ans + term) % MOD; } } return ans; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin >> T; for (int tc = 1; tc <= T; ++tc) { ll n, m, K; cin >> n >> m >> K; ll ans; if (n == 1 && m == 1) { ans = K % MOD; } else { int p = (int)(n + m - 2); ll S = sum_pow(K - 1, p); ll ways = mod_pow(K, (n - 1) * (m - 1)); ans = (n % MOD) * (m % MOD) % MOD; ans = ans * ways % MOD; ans = ans * S % MOD; } cout << "Case #" << tc << ": " << ans << '\n'; } return 0; }

4.2 赛场最容易踩的三个坑

第一个坑是取模运算的顺序。n 和 m 最多 2000，乘起来不超过 4×10^6，直接乘不会爆 int，但在后续乘 K^((n-1)(m-1)) 和 S 时，中间结果会超过 long long 的范围吗？MOD 是 1e9+7，两个 MOD 内的数相乘大约是 1e18，刚好在 long long 上限 9.22e18 之内，所以每次都取模就没问题。关键在于不要等所有项乘完再取模，每一步乘法都要跟一个 % MOD。

第二个坑是负数取模。插值公式里会出现 k - j，当 k 比较小而 j 比较大时，k - j 是负数。C++ 里负数取模得到的结果还是负数，直接乘到 mod 数上会导致答案错误。所以代码里写 ((k - i) % MOD + MOD) % MOD，先调整成非负再参与乘法。这个细节很容易疏忽，但对拍时一般能抓出来。

第三个坑是输出格式。Gym 题通常要求输出 “Case #x: ans”，注意大小写、井号、冒号后面有空格。很多人在这种地方白白吃一个 Presentation Error，非常冤。提交前先看样例输出格式，或者直接复制样例格式。

4.3 小数据对拍思路

写完代码后，我习惯写一个暴力枚举程序来对拍。暴力程序就直接三层循环枚举 n×m 网格里每个格子的值，然后判断好格子数量，累加答案。对拍时随机生成 n,m,K 都很小的数据，比如 n,m≤3，K≤3，比较暴力结果和公式结果。

下面这个验证可以在本地快速跑：

• 输入 T=1，n=1，m=3，K=3。手算一下，1×3 网格，每个格子只与另外两个格子比较。固定一个格子，值为 x 时，另外两个格子必须都小于 x，所以概率是 sum_{x=1}^{3} (x-1)^2 / 3^2 = (0+1+4)/9=5/9。期望好格子数 = 3×5/9=5/3。总方案数 27，所以总和 = 27×5/3=45。用代码算：p=2，sum=0^2+1^2+2^2=5，ways=3^0=1，ans=3×1×5=15？等等，这里出错了。

等等，重新算一下。n=1,m=3,K=3。公式是 n×m × K^((n-1)(m-1)) × sum i^p。n×m=3，K^((0)(2))=3^0=1，p=1+3-2=2，sum=0^2+1^2+2^2=5。ans=3×1×5=15。但我上面口算期望是 5/3，总方案 27，27×5/3=45。15 和 45 对不上，说明我口算期望错了。

重新算：固定一个格子，值为 x 时，另外 n+m-2=2 个格子都小于 x。如果 x=1，没有选择；x=2，另外两个都是1，概率 (1/3)^2=1/9；x=3，另外两个在{1,2}中，概率 (2/3)^2=4/9。所以 P=1/9+4/9=5/9。3 个格子，E=3×5/9=5/3。总方案 3^3=27，总好格子数=27×5/3=45。

公式算出来却是 15，说明公式有问题？让我重新推。

公式推导：固定格子是好格子的事件包含方案数： sum_x (x-1)^(n+m-2) × K^((n-1)(m-1)) = sum_x (x-1)^2 × 3^0 = (0+1+4)=5。 总方案 27，P=5/27，不是 5/9！啊，我之前约分时错了。K^(nm)=3^3=27，K^(n+m-1)=3^(1+3-1)=3^3=27，K^((n-1)(m-1))=3^0=1，约分后 P=sum/K^(n+m-1)，而 K^(n+m-1)=27，所以 P=5/27。期望=3×5/27=5/9。总答案=27×5/9=15。公式 15 是对的。我之前的“另外两个格子都小于 x 的概率 (1/3)^2=1/9”错了，因为要乘格子值为 x 的概率 1/3。x=2 时，P(格子值=2 且另外两个=1) = (1/3)×(1/3)^2 = 1/27，x=3 时 = (1/3)×(2/3)^2 = 4/27，总 P=5/27。这就对了。

所以代码跑出来应该是 15。这提醒我们，手算验证也要小心条件概率。我上面差点被错误口算带偏。

4.4 复杂度分析

整个算法分两部分：预处理节点 y[0..d] 需要 d 次快速幂，d=p+1=n+m-1，每次快速幂 O(log p)，所以这一部分 O((n+m) log(n+m))；拉格朗日插值部分 O(d)。总体可以认为是 O((n+m) log MOD)，非常快。空间上只需要几个长度为 O(n+m) 的数组，内存完全不是问题。

如果把 d 放宽到 10^5，预处理部分的 O(d log MOD) 也还能跑，但如果 p 更大，可以考虑用线性筛预处理所有 i^p，把复杂度降到 O(d)。不过这题用不到，知道有这个优化方向就行。

5. 复盘：这类思维题到底在考什么

5.1 期望线性性是一个被低估的武器

很多选手学期望时，总是被“事件独立”“条件概率”这些概念困住，结果遇到计数题想不到用期望。实际上，求“所有方案中某个指标的总和”时，期望线性性是第一选择，因为线性性不要求事件独立。

类似的应用场景非常多。比如随机排列中逆序对的期望数，各位置之间明显不独立，但 E[逆序对总数] = sum_{i<j} P(i 在 j 前面) = C(n,2)/2。再比如随机图中三角形个数的期望，也是把每个三元组是否构成三角形拆开算。Great Cells 这题就是同一个套路套在网格模型上。

以后看到“所有方案中满足某性质的元素数量总和”这种题，先别急着想容斥，先问自己一句：能不能把每个元素是不是满足性质拆开算概率，再用线性性加起来？大多数时候答案是可以。

5.2 自然数幂和：别只会背公式

自然数幂和是竞赛里出现频率很高的一个点。低次时可以直接背公式，但 p 一大，背伯努利数公式不现实，用拉格朗日插值就非常通用。只需要知道“sum i^p 是 p+1 次多项式”这一个结论，配合连续整点插值的技巧，就能处理几乎所有 k 很大的幂和问题。

顺便提一个细节：这题的 p = n+m-2，最大 4000 左右。有些人可能会想用指数生成函数或多项式求逆，那些方法适合 p 到 10^5 甚至 10^6 的场景，在这题属于过度设计。比赛时要根据数据范围选最合适的工具，而不是选最炫的工具。

5.3 赛场上怎么分配时间

这题在区域赛里大概是中等偏上的难度，完整推导加代码，熟练的话 20 到 30 分钟能搞定。建议的思考路径是：

• 看到计数总和，先套期望线性性；
• 算单格概率，得到 ans = n×m×K^((n-1)(m-1))×sum i^p；
• 看到 sum i^p 且 K 很大，立刻想到拉格朗日插值；
• 模板直接上，注意 p=0 的边界。

如果推了 15 分钟还没理清头绪，大概率是卡在“没想到期望线性性”这一步。这时候可以换一种问法：每个格子对答案的贡献是多少？把格子当成元素，贡献独立拆开算，本质还是线性性。

我个人觉得，区域赛里“数学推导/思维”标签的题，很多时候并不是要你掌握什么高深数学，而是要把几个学过的、看起来基础的工具组合起来。期望线性性和自然数幂和插值，单独拿出来都很基础，但组合在一道网格计数题里，就成了很多人的拦路虎。这题值得多刷几遍，直到你能不看公式独立推完一遍为止。

最后再说一个我补题时的习惯：每推完一个公式，一定手动代入一个小样例，哪怕题目样例里已经有了，我也会自己再构造一个更小的例子。因为公式推导过程里很容易出现“少乘一个概率”“指数写反”这类低级错误，小样例基本都能当场抓出来。Great Cells 这题我就在 1×3,K=3 这个例子上栽过一次，差点把错误的期望公式带入代码。建议大家也养成这个习惯，公式和代码写完，先跑小数据验证，再交，能省不少罚时。