在信奥刷题打卡表里翻到第3004题时文件名里的 P6202 [USACO07CHN] Summing Sums G 让我以为又是一道模拟或者贪心。题面翻译过来很简单有 N 个数排成一排每个数初始值给定每一轮把每个数替换成“当前所有其他数的和”一共重复 T 轮要求最后每个数的值。我第一反应是两层循环直接做但看了一眼数据范围立刻打消了这个念头T 和 N 都大得离谱肯定要找规律。这篇文章就把这道题的完整推导、模运算处理、C 代码和踩坑记录都写出来适合正在准备 CSP/NOIP、刷 USACO或者想练一练“先推公式再快速幂”这类套路的同学。这道题的价值不在代码量而在推导过程。它背后是一个线性变换只要能把每轮操作抽象成矩阵或者递推式答案几乎就摆在你面前了。下面我按自己的思路从头过一遍尽量不用高深的数学语言保证能跟着一步步写出来。1. 题目讲的是什么别一上来就暴力模拟1.1 题面解读题目的设定是 N 个数字不妨直接叫它们 a_0, a_1, ..., a_{N-1}。每次操作对于位置 i新的值等于所有其他位置当前值的和x_i S - x_i其中 S 是本轮开始时的总和。注意这里“其他所有数”不包括自己所以公式里是“总和减掉自己”。这个操作重复 T 次。如果 T 特别小N 特别小两层循环没有任何问题。但这类题目既然放到 Gold 级别T 通常不会给你留活路常见的范围是 10^9 甚至更大N 也可能上万O(NT) 的模拟基本不可能通过。所以第一步必须先看数据范围然后立刻转向数学推导。举个例子如果输入格式是这样的3 2 1 2 3手工跑两轮初始总和 6第一轮每个数变成“总和减自己”5 4 3。第二轮当前总和 12每个数变成“总和减自己”7 8 9。看起来不难但一旦 T 变成 10^9手工模拟就是笑话了。这道题真正问的是你能不能从三轮、四轮的运算里抽出一个通项公式。1.2 为什么模拟走不通我帮大家算笔账。假设 N 50000T 10^9直接模拟需要 5 * 10^13 次基本操作。现代 C 的常数再小一秒撑死跑 10^8 量级这已经是几十个小时的运算量。哪怕你开 O2也无济于事。更麻烦的是每轮要用“上一轮的完整状态”更新下一轮你还得额外复制一遍数组内存带宽又拖后腿。还有一点如果你真的把每一轮所有值都算出来中间结果很快就会变成天文数字因为总和每轮都在乘 (N-1)很快就爆 long long。所以模拟除了慢还面临溢出的问题。看到这种信号就应该知道题目考察的一定是“压缩信息”的能力而不是考察你会不会写循环。1.3 关键观察操作是线性的这题的核心观察就是每次操作都是对向量 x (x_1, x_2, ..., x_N)^T 做一次线性变换。你可以用一个 N 阶矩阵 M 来表示M 的每个对角线元素是 0非对角线元素是 1。那么一轮操作就是x^{(t1)} M x^{(t)}矩阵看起来很吓人但不要慌。M 其实可以拆成两个简单东西所有元素都是 1 的矩阵 J 减掉单位矩阵 I即 M J - I。为什么要拆成 J 和 I因为 J 这个矩阵非常特殊任何向量乘上 J得到的向量每个分量都等于原向量的总和。而且 J 的平方等于 N 倍的 J也就是说 J 的高次幂总能化回 J 本身不会越变越复杂。再加上 J 和 I 可以交换整个 (J-I) 的任意次方都能化简成“某个数乘 I 加上另一个数乘 J”的形式。这个性质直接决定了答案的结构每个位置最后的值一定是“自己的初始值乘一个系数加上全体初始总和乘另一个系数”。这就是后面所有推导的基础。2. 数学推导把T轮后的答案写成一个公式2.1 总和的变化S每轮乘(N-1)先算总和。设第 t 轮开始前所有数的和为 S_t那么一轮之后S_{t1} sum_i (S_t - x_i^{(t)}) N * S_t - S_t (N-1) * S_t这个式子太重要了。它说明总和的变化和具体每个数是多少根本无关只取决于上轮总和。所以立刻有S_t (N-1)^t * S_0也就是说T 轮之后的总和是初始总和的 (N-1)^T 倍。这其实也解释了为什么中间结果会爆炸同时也给了我们第一个关键参数。我用一个生活化的类比来解释想象你有一个账户总额 S每次“分红”是把总额分给 N 个人但每个人拿到的不是等额红包而是“总额减掉自己手里的钱”。不管每个人手里怎么变下一轮账户总额永远等于上一轮的 (N-1) 倍。这个倍数只取决于人数和谁拿了多少钱完全无关。2.2 每个数的通用形式(-1)^T乘自己再加一个公共项有了总和的变化规律再回到单个数的转移式x_i^{(t1)} S_t - x_i^{(t)}现在把 S_t 用 (N-1)^t S_0 代入。直觉上每个数每一轮都要被“总和减自己”更新一次而总和又在指数增长所以 x_i^{(t)} 应该能表示成“初始值乘以某个系数 S_0 乘以某个系数”。因为整个过程对每个位置是对称的系数不依赖 i只依赖轮数。于是大胆设x_i^{(t)} p_t * x_i^{(0)} q_t * S_0其中 p_t 是“自己初始值”的系数q_t 是“公共总和”的系数。把这一形式代回递推式x_i^{(t1)} (N-1)^t S_0 - (p_t x_i^{(0)} q_t S_0)整理一下x_i^{(t1)} -p_t x_i^{(0)} ((N-1)^t - q_t) S_0跟通用形式对比得到两组递推p_{t1} -p_tq_{t1} (N-1)^t - q_t初始时 t0显然 x_i^{(0)} 1 * x_i^{(0)} 0 * S_0所以 p_01q_00。p 的递推非常简单每轮变一次号所以 p_t (-1)^t。这个结论的直觉是如果只有两个数那么每轮就是在“原数”和“总和减原数”之间交替符号当然会翻转。q 的递推稍微麻烦一点q_{t1} q_t (N-1)^t这是一个带指数的线性非齐次递推。我们可以把它展开q_t (N-1)^{t-1} - (N-1)^{t-2} (N-1)^{t-3} - ... (-1)^{t-1} (N-1)^0这个交错等比级数的公比是 -1/(N-1)。用等比数列求和公式一算得到q_t ((N-1)^t - (-1)^t) / N为了确认没有推导错可以代入小 t 验证t1 时 q_1 ((N-1) 1)/N 1这正好对应一轮后每个数都是“总和减自己”系数确实为 1。t2 时 q_2 ((N-1)^2 - 1)/N N-2也和我们手推的结果一致。公式没问题。所以最终答案就是x_i^{(T)} (-1)^T x_i^{(0)} [((N-1)^T - (-1)^T) / N] * S_0到这一步问题已经从“模拟 T 轮”变成了“算一个幂、一次除法、一次乘法和一次加法”复杂度从 O(NT) 掉到 O(N log T)。2.3 这个公式的矩阵解释上面是用递推法推的可能有人会问为什么 p_t 和 q_t 一定存在其实用矩阵更好理解。x^{(t)} (J-I)^t x^{(0)}。因为 J^2 N J所以任何 (J-I)^t 展开后都能化简成 p_t I q_t J 的形式p_t 和 q_t 就是对应系数。而矩阵 J-I 有两个特征值方向 (1,1,...,1) 上对应特征值 N-1其他方向上对应特征值 -1。这两个特征值正好就是 p_t 和 q_t 公式里出现的 (N-1)^t 和 (-1)^t。很多选手第一反应是“那就对 N 维矩阵做矩阵快速幂”但 N 可能到几万根本存不下。正确的做法是把矩阵快速幂的结果“压缩”成 I 和 J 的线性组合只维护两个系数。这个思路值得记下来很多类似题都是这么干的。2.4 公式的验证拿小样例手推我习惯在写完公式后拿小样例验证这一步能省下后面 debug 的大量时间。比如 N3初始 a[1,2,3]T2。手动模拟初始总和 6第一轮每个数变成 6-自己得到 5 4 3。第二轮当前总和 12每个数变成 12-自己得到 7 8 9。用公式算S_06(N-1)^T2^24(-1)^T1q_T(4-1)/31。所以x_i^{(2)} (1) * a_i 1 * 6对 1 得 7对 2 得 8对 3 得 9。和手推完全一致。再验证 T1q_1(21)/31x_i^{(1)} -a_i 6得到 5 4 3。也对。所以公式在逻辑上自洽可以放心写代码。3. C实现从公式到代码只有一步3.1 快速幂和乘法逆元代码里需要两样东西快速幂和模逆元。快速幂用来算 (N-1)^T mod MOD底数是 N-1指数是 TT 用 long long 存。模逆元用来处理公式里的除以 N。在模为质数的情况下根据费马小定理a 的模逆元等于 a^(MOD-2) mod MOD所以直接再调用一次快速幂就行。为什么要取模题目输出的答案通常在某个模数下而且如果不取模T 大一点中间数就完全存不下了。这里我用常见的 1,000,000,007 作为示例模数如果题面指定了别的模数只要改掉 const ll MOD 那一行并把 N 和初值的读入后也同步取模即可。快速幂的实现其实就是一个“二进制分解指数”的过程。计算 a^b 的时候把 b 看成二进制位如果当前位是 1就乘上对应的 a 的幂每一轮都把 a 平方一下。这样最多循环 log b 次而不是 b 次。这是算法竞赛里最基础也最常用的小工具建议哪怕闭着眼睛也要写得出来。3.2 完整代码下面是我最终提交用的 C 代码核心思想和上面推导完全对应。我加了比较详细的注释方便直接对着看#include bits/stdc.h using namespace std; typedef long long ll; const ll MOD 1000000007LL; ll qpow(ll a, ll b) { ll res 1 % MOD; a % MOD; while (b 0) { if (b 1LL) res res * a % MOD; a a * a % MOD; b 1; } return res; } ll inv(ll x) { return qpow(x, MOD - 2); // 费马小定理要求 MOD 为质数 } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; ll T; cin N T; vectorll a(N); ll S0 0; for (int i 0; i N; i) { cin a[i]; a[i] (a[i] % MOD MOD) % MOD; S0 (S0 a[i]) % MOD; } ll powNm1 qpow((N - 1) % MOD, T); // (N-1)^T ll sign (T 1LL) ? (MOD - 1) : 1; // (-1)^T 在模 MOD 下的表示 ll common (powNm1 - sign MOD) % MOD; // 先算分子 common common * inv(N) % MOD; // 再乘 N 的逆元得到 q_T for (int i 0; i N; i) { ll part1 (T 1LL) ? (MOD - a[i]) % MOD : a[i]; // (-1)^T * a_i ll ans (part1 common * S0 % MOD) % MOD; if (i) cout ; cout ans; } cout \n; return 0; }几点说明sign 那行比较关键。在模意义下(-1)^T 如果是奇数就是 MOD-1偶数就是 1。我直接判断 T 的二进制最低位省得多写一个快速幂。common 先减后加 MOD 是为了处理负数得到正确的模值。如果原题没有模数、要求精确输出并且 T 很小那就不需要逆元直接把取模部分去掉用高精度或者 long long 算分子再除以 N 也可以。但绝大多数情况下这种题一定会给模数。3.3 代码里的几个细节第一快速幂的指数类型。T 可能超过 int我直接声明成 long long。比赛中我见过有人 int T 读入导致溢出WA 得莫名其妙。第二读入初值时立刻取模。初值可能很大也可能是负数。这里用 (a[i] % MOD MOD) % MOD 统一转成正数。第三累加 S0 时也要取模。S0 是公式中的关键一旦溢出后面全错。第四输出答案前再取一次模保证每个输出都在 [0, MOD) 区间。另外这里有一个很容易忽略的数学细节q_T 的计算是“先算分子再乘逆元”。由于分子 ((N-1)^T - (-1)^T) 在整数意义下一定被 N 整除但在模意义下你没法直接做整数除法只能乘逆元。所以顺序很重要不能先对 N 取模再逆元也不能把逆元乘到指数上。4. 实战过程中最容易踩的坑4.1 负数取模C 里负数的 % 运算是保留符号的比如 (-1) % 1000000007 在大多数编译器上结果是 -1而不是 1000000006。所以凡是可能出现负数的地方我都统一先加 MOD 再取模。这个坑在代码里我已经处理了但自己写的时候很容易漏尤其是求 sign 和 (powNm1 - sign MOD) % MOD 这种表达式。我一开始写的时候直接写了 powNm1 - sign没有加 MOD结果样例里 T 为奇数时答案全错。排查了半天才发现是负数取模的问题。这个问题在 C 里很经典也是很多入门选手经常栽跟头的地方。4.2 逆元不存在的情况费马小定理求逆元的前提是 MOD 是质数并且要除的数这里是 N不是 MOD 的倍数。如果题目的模数是合数比如某些题喜欢用 10^87 或者 998244353 以外的奇怪数字那需要先判断 gcd(N, MOD) 是否等于 1然后用扩展欧几里得求逆元。更保险的做法是盯着题目条件模数是不是质数。我在写这题时默认了质数模数所以直接上了费马小定理实际上也能过。如果你在比赛中遇到一个不确定的模数稳妥的做法是在读入 N 后先调用一次 std::gcd(N, MOD)如果 gcd 不为 1说明 N 在模意义下不可逆这时候要么换思路要么用中国剩余定理之类的工具拆开算。不过竞赛里出题人一般会避免这种情况否则题目难度就完全跑偏了。4.3 边界情况自查表我在提交前会习惯性过一遍边界这道题值得检查的有这么几个情况预期结果代码表现T0直接输出原数组sign1powNm11common0输出原值N1, T0每个数每轮都变成空和即 0(N-1)^T0sign 无关紧要公式算出来是 0N1, T0输出原值同上边界输出原值初值有负数先转正再计算读入时统一转正T 为奇数自己的系数是 -1sign 取 MOD-1其中 N1 的情况是个隐藏坑。很多人会因为“其他所有数”为空而困惑公式里 N-100 的 0 次方在快速幂里我让 qpow 返回 1正好保证了 T0 时正确T 大于 0 时 0^T0最后算出全 0也正确。还有初值为负数的情况。我第一版代码没有对 a[i] 做负数修正导致 S0 变成了一个巨大的正数因为负数取模得到的是负数累加多了就错。这种错误特别隐蔽因为小样例可能恰好没有负数。4.4 时间复杂度与数据范围整份代码的代价是一次快速幂 O(log T) 和一次线性扫描 O(N)总复杂度 O(N log T)。这个复杂度在 N10^5、T10^18 的情况下也非常稳。快速幂内部的乘法全部在 mod 意义下进行中间值不超过 MOD^2用 long long 足够存不会溢出。如果 T 再大甚至超过 long long那就需要用字符串读入再配合欧拉降幂不过那是极少数情况了。我还想提一个和初始数组大小有关的点如果 N 很大vector 的空间是可控的没必要开普通数组。用 vector 的好处是不用手动管理内存也不会因为数组开小了越界。如果你习惯用 C 风格数组一定要看清题目里 N 的上限开数组时留出余量。5. 这道题带给我的启发我最初看到“求和”题第一反应是维护前缀和或者模拟结果走了弯路。后来把操作矩阵拆成 J 和 I一切才开始清晰起来。这个“把复杂矩阵幂化简成两个系数”的思路对我后续刷其他线性递推题帮助很大。最后再分享一个小技巧遇到这种 T 巨大的轮换操作题先不要急着写代码试着在纸上算三轮、四轮看每个数和自己初始值、总和的系数有没有规律。一旦发现 p 和 q 是分开迭代的公式基本就到手了。信奥刷题打卡到第 3004 个最大的体会就是很多看似简单的题卡住的不是代码而是你愿不愿意停下来先推两步数学。