先给结论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 很小比如 K2nm3也有 2^9512 种方案勉强能枚举但题目里 K 可以到 1e9n、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)^(nm-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_{x1}^{K} (x-1)^(nm-2) × K^((n-1)(m-1))总方案数是 K^(n×m)所以固定格子是好格子的概率为P [ sum_{x1}^{K} (x-1)^(nm-2) × K^((n-1)(m-1)) ] / K^(n×m)将分母拆开K^(n×m) K^(nm-1) × K^((n-1)(m-1))因为 nm-1 (n-1)(m-1) nm。于是上下约掉 K^((n-1)(m-1))得到P sum_{x1}^{K} (x-1)^(nm-2) / K^(nm-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_{x1}^{K} (x-1)^(nm-2)令 i x - 1那么 i 从 0 取到 K - 1最终公式答案 n×m × K^((n-1)(m-1)) × sum_{i0}^{K-1} i^(nm-2)到这一步原问题已经变成了一个纯粹的数学问题计算 sum_{i0}^{K-1} i^p其中 p n m - 2。这里再补充一个有趣的观察两个好格子不可能在同一行或同一列。因为如果同一行有两个好格子 A 和 B那么 A 是好格子要求 A 的值大于 B 的值B 是好格子又要求 B 的值大于 A 的值矛盾列同理。所以好格子只能分布在行列互不相同的位置。这个观察在算概率时不是必需的但能帮助理解为什么用“单格概率 × 格子数”不会重复计算——线性性本身已经把重合的情况都处理好了。2.3 代入小数据验证公式对不对公式推出来之后强烈建议先拿小数据手算一遍确认没有推错方向。例 1n1m2K2。总共有 2^24 种方案(1,1)第二个格子值为 1与第一个格子相等没有好格子(1,2)第二个格子值为 2严格大于第一个格子的 1所以它是好格子数量 1(2,1)第一个格子值为 2是好格子数量 1(2,2)两个格子都为 2没有严格大于关系数量 0。总和是 2。代入公式n×m2K^((n-1)(m-1))2^01sum_{i0}^{1} i^(12-2)0^11^11答案是 2。一致。例 2n2m2K2。总共 2^416 种方案。固定一个格子值为 2 且同行同列两个格子都为 1 时它才是好格子概率为 (1/2)×(1/2)^21/8。期望好格子数为 4×1/81/2。总答案16×1/28。代入公式4×2^(1×1)×(0^21^2)4×2×18。一致。两个例子都对说明公式大概率没问题。接下来真正的工作重心就落在怎么快速求 sum_{i0}^{K-1} i^p。3. 自然数幂和从暴力到拉格朗日插值3.1 什么时候可以直接暴力累加如果 K 很小比如 K ≤ 2000 或者 K ≤ 10^5直接 for 循环加快速幂完全可行。复杂度是 O(K log p)在 K 不大的时候能轻松通过。但本题的 K 可以到 1e9p n m - 2 最大可以到 4000 左右。如果直接循环到 1e9每次快速幂 log p 大约 12 次乘法总操作数在 10^10 级别必然超时。所以必须找数学方法。这里的“数学方法”不是去背伯努利数公式而是用一个更通用的结论自然数幂和是一个多项式。具体来说sum_{i0}^{k} i^p 是关于 k 的 p1 次多项式。比如sum_{i0}^{k} i k(k1)/2是 2 次多项式sum_{i0}^{k} i^2 k(k1)(2k1)/6是 3 次多项式一般地F(k) sum_{i0}^{k} i^p 是 p1 次多项式。这个结论的严格证明可以用有限差分或者伯努利多项式但竞赛里记住结论就行。既然 F(k) 是 d p1 次多项式那么只要知道 d1 p2 个点上的函数值就能唯一确定这个多项式进而求出任意 k 处的值。这正是拉格朗日插值的用武之地。我们不需要真的把多项式系数解出来只需要在 k K-1 处直接插值求值。3.2 为什么可以用拉格朗日插值拉格朗日插值的基本思想是给定 d1 个节点 (x_0, y_0), (x_1, y_1), ..., (x_d, y_d)可以构造一个 d 次多项式满足这些点的取值并且在其他点上有定义。对于本题我们选取节点 x_j jj 0, 1, ..., d对应的 y_j F(j) sum_{i0}^{j} i^p。这里 d p1所以一共有 p2 个节点。这些 y_j 值可以暴力算从 0 到 d每次用快速幂算 j^p再累加。因为 d 不超过 4000这部分复杂度完全可以接受。拉格朗日插值公式是F(k) sum_{j0}^{d} y_j × prod_{t≠j} (k - x_t) / (x_j - x_t)直接按这个公式做每次求分母和分子都是 O(d)总复杂度 O(d^2)。d4000 时是 1.6×10^7其实也能跑但没必要。利用“节点是连续整数”这一特殊性质可以把复杂度降到 O(d)。3.3 连续整点节点的优化技巧阶乘与前后缀积因为 x_t t所以分母可以显式化简。对固定的 jprod_{t0, t≠j}^{d} (j - t) [prod_{t0}^{j-1} (j - t)] × [prod_{tj1}^{d} (j - t)]前半部分是 j × (j-1) × ... × 1 j!。后半部分是 (-1) × (-2) × ... × (j-d) 写成(j - (j1)) × (j - (j2)) × ... × (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_{t0}^{j} (k - t)suf[j] prod_{tj}^{d} (k - t)。那么排除 tj 的乘积就是 pre[j-1] × suf[j1]前后各乘一遍即可O(1) 得到分子。把分子和分母拼起来再处理符号 (-1)^(d-j)就能在 O(d) 时间内完成插值。有一个注意点如果 k 恰好落在某个节点上即 K-1 在 0 到 d 之间直接用 y_{K-1} 返回就行不需要插值。原因是插值公式里会出现 (k-j)0 导致分子变 0虽然最后结果会因为 y_j 恰好等于目标值而不出错但实现时特判更干净。3.4 边界情况nm1 时 p0 的问题这题最容易被忽视的边界是 nm1。此时网格只有一个格子这个格子没有同行同列的其他格子“严格大于所有同行同列格子”的条件为空真所以它一定是好格子。总共有 K 种填法答案显然是 K。带入公式n×m1K^((n-1)(m-1))K^01pnm-20于是需要计算 sum_{i0}^{K-1} i^0。问题来了i0 时 0^0 在数学上通常约定为 1因为每个格子都是好格子。但如果程序里直接用 pow_mod(0, 0)不同实现可能返回 0 或 1容易出错。稳妥的做法是在实现自然数幂和时单独特判 p0直接返回 K % MOD。这样既避免了 0^0 的歧义也让代码逻辑更清晰。4. 代码落地从公式到 AC4.1 完整 C17 实现下面这份代码是完整可提交的版本。核心函数 sum_pow(k, p) 计算 sum_{i0}^{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_{i0}^{k} i^p mod MOD // 要求 p 1p0 时在外部特判 ll sum_pow(ll k, int p) { int d p 1; // F(k) 是 p1 次多项式需要 d1 个点 vectorll 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 快速求 vectorll 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 是 1e97两个 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≤3K≤3比较暴力结果和公式结果。下面这个验证可以在本地快速跑输入 T1n1m3K3。手算一下1×3 网格每个格子只与另外两个格子比较。固定一个格子值为 x 时另外两个格子必须都小于 x所以概率是 sum_{x1}^{3} (x-1)^2 / 3^2 (014)/95/9。期望好格子数 3×5/95/3。总方案数 27所以总和 27×5/345。用代码算p2sum0^21^22^25ways3^01ans3×1×515等等这里出错了。等等重新算一下。n1,m3,K3。公式是 n×m × K^((n-1)(m-1)) × sum i^p。n×m3K^((0)(2))3^01p13-22sum0^21^22^25。ans3×1×515。但我上面口算期望是 5/3总方案 2727×5/345。15 和 45 对不上说明我口算期望错了。重新算固定一个格子值为 x 时另外 nm-22 个格子都小于 x。如果 x1没有选择x2另外两个都是1概率 (1/3)^21/9x3另外两个在{1,2}中概率 (2/3)^24/9。所以 P1/94/95/9。3 个格子E3×5/95/3。总方案 3^327总好格子数27×5/345。公式算出来却是 15说明公式有问题让我重新推。公式推导固定格子是好格子的事件包含方案数 sum_x (x-1)^(nm-2) × K^((n-1)(m-1)) sum_x (x-1)^2 × 3^0 (014)5。 总方案 27P5/27不是 5/9啊我之前约分时错了。K^(nm)3^327K^(nm-1)3^(13-1)3^327K^((n-1)(m-1))3^01约分后 Psum/K^(nm-1)而 K^(nm-1)27所以 P5/27。期望3×5/275/9。总答案27×5/915。公式 15 是对的。我之前的“另外两个格子都小于 x 的概率 (1/3)^21/9”错了因为要乘格子值为 x 的概率 1/3。x2 时P(格子值2 且另外两个1) (1/3)×(1/3)^2 1/27x3 时 (1/3)×(2/3)^2 4/27总 P5/27。这就对了。所以代码跑出来应该是 15。这提醒我们手算验证也要小心条件概率。我上面差点被错误口算带偏。4.4 复杂度分析整个算法分两部分预处理节点 y[0..d] 需要 d 次快速幂dp1nm-1每次快速幂 O(log p)所以这一部分 O((nm) log(nm))拉格朗日插值部分 O(d)。总体可以认为是 O((nm) log MOD)非常快。空间上只需要几个长度为 O(nm) 的数组内存完全不是问题。如果把 d 放宽到 10^5预处理部分的 O(d log MOD) 也还能跑但如果 p 更大可以考虑用线性筛预处理所有 i^p把复杂度降到 O(d)。不过这题用不到知道有这个优化方向就行。5. 复盘这类思维题到底在考什么5.1 期望线性性是一个被低估的武器很多选手学期望时总是被“事件独立”“条件概率”这些概念困住结果遇到计数题想不到用期望。实际上求“所有方案中某个指标的总和”时期望线性性是第一选择因为线性性不要求事件独立。类似的应用场景非常多。比如随机排列中逆序对的期望数各位置之间明显不独立但 E[逆序对总数] sum_{ij} P(i 在 j 前面) C(n,2)/2。再比如随机图中三角形个数的期望也是把每个三元组是否构成三角形拆开算。Great Cells 这题就是同一个套路套在网格模型上。以后看到“所有方案中满足某性质的元素数量总和”这种题先别急着想容斥先问自己一句能不能把每个元素是不是满足性质拆开算概率再用线性性加起来大多数时候答案是可以。5.2 自然数幂和别只会背公式自然数幂和是竞赛里出现频率很高的一个点。低次时可以直接背公式但 p 一大背伯努利数公式不现实用拉格朗日插值就非常通用。只需要知道“sum i^p 是 p1 次多项式”这一个结论配合连续整点插值的技巧就能处理几乎所有 k 很大的幂和问题。顺便提一个细节这题的 p nm-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 很大立刻想到拉格朗日插值模板直接上注意 p0 的边界。如果推了 15 分钟还没理清头绪大概率是卡在“没想到期望线性性”这一步。这时候可以换一种问法每个格子对答案的贡献是多少把格子当成元素贡献独立拆开算本质还是线性性。我个人觉得区域赛里“数学推导/思维”标签的题很多时候并不是要你掌握什么高深数学而是要把几个学过的、看起来基础的工具组合起来。期望线性性和自然数幂和插值单独拿出来都很基础但组合在一道网格计数题里就成了很多人的拦路虎。这题值得多刷几遍直到你能不看公式独立推完一遍为止。最后再说一个我补题时的习惯每推完一个公式一定手动代入一个小样例哪怕题目样例里已经有了我也会自己再构造一个更小的例子。因为公式推导过程里很容易出现“少乘一个概率”“指数写反”这类低级错误小样例基本都能当场抓出来。Great Cells 这题我就在 1×3,K3 这个例子上栽过一次差点把错误的期望公式带入代码。建议大家也养成这个习惯公式和代码写完先跑小数据验证再交能省不少罚时。