在信奥刷题打卡表里翻到第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 = 50000，T = 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^{(t+1)} = 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_{t+1} = 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^{(t+1)} = 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^{(t+1)} = (N-1)^t S_0 - (p_t x_i^{(0)} + q_t S_0)
整理一下：
x_i^{(t+1)} = -p_t x_i^{(0)} + ((N-1)^t - q_t) S_0
跟通用形式对比，得到两组递推：
p_{t+1} = -p_t
q_{t+1} = (N-1)^t - q_t
初始时 t=0，显然 x_i^{(0)} = 1 * x_i^{(0)} + 0 * S_0，所以 p_0=1，q_0=0。
p 的递推非常简单，每轮变一次号，所以 p_t = (-1)^t。这个结论的直觉是：如果只有两个数，那么每轮就是在“原数”和“总和减原数”之间交替，符号当然会翻转。
q 的递推稍微麻烦一点：
q_{t+1} + 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 验证：t=1 时 q_1 = ((N-1) + 1)/N = 1，这正好对应一轮后每个数都是“总和减自己”，系数确实为 1。t=2 时 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 的大量时间。比如 N=3，初始 a=[1,2,3]，T=2。
手动模拟：
- 初始总和 6，第一轮每个数变成 6-自己，得到 5 4 3。
- 第二轮当前总和 12，每个数变成 12-自己，得到 7 8 9。
用公式算：S_0=6，(N-1)^T=2^2=4，(-1)^T=1，q_T=(4-1)/3=1。所以：
x_i^{(2)} = (+1) * a_i + 1 * 6
对 1 得 7，对 2 得 8，对 3 得 9。和手推完全一致。
再验证 T=1：q_1=(2+1)/3=1，x_i^{(1)} = -a_i + 6，得到 5 4 3。也对。所以公式在逻辑上自洽，可以放心写代码。
3. C++实现：从公式到代码只有一步
3.1 快速幂和乘法逆元
代码里需要两样东西：快速幂和模逆元。快速幂用来算 (N-1)^T mod MOD，底数是 N-1，指数是 T，T 用 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; vector<ll> 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^8+7 或者 998244353 以外的奇怪数字，那需要先判断 gcd(N, MOD) 是否等于 1，然后用扩展欧几里得求逆元。更保险的做法是盯着题目条件：模数是不是质数。我在写这题时默认了质数模数，所以直接上了费马小定理，实际上也能过。
如果你在比赛中遇到一个不确定的模数，稳妥的做法是在读入 N 后先调用一次 std::gcd(N, MOD)，如果 gcd 不为 1，说明 N 在模意义下不可逆，这时候要么换思路，要么用中国剩余定理之类的工具拆开算。不过竞赛里出题人一般会避免这种情况，否则题目难度就完全跑偏了。
4.3 边界情况自查表
我在提交前会习惯性过一遍边界，这道题值得检查的有这么几个：
| 情况 | 预期结果 | 代码表现 |
|---|---|---|
| T=0 | 直接输出原数组 | sign=1，powNm1=1，common=0，输出原值 |
| N=1, T>0 | 每个数每轮都变成空和，即 0 | (N-1)^T=0，sign 无关紧要，公式算出来是 0 |
| N=1, T=0 | 输出原值 | 同上边界，输出原值 |
| 初值有负数 | 先转正再计算 | 读入时统一转正 |
| T 为奇数 | 自己的系数是 -1 | sign 取 MOD-1 |
其中 N=1 的情况是个隐藏坑。很多人会因为“其他所有数”为空而困惑，公式里 N-1=0，0 的 0 次方在快速幂里我让 qpow 返回 1，正好保证了 T=0 时正确；T 大于 0 时 0^T=0，最后算出全 0，也正确。
还有初值为负数的情况。我第一版代码没有对 a[i] 做负数修正，导致 S0 变成了一个巨大的正数，因为负数取模得到的是负数，累加多了就错。这种错误特别隐蔽，因为小样例可能恰好没有负数。
4.4 时间复杂度与数据范围
整份代码的代价是一次快速幂 O(log T) 和一次线性扫描 O(N)，总复杂度 O(N + log T)。这个复杂度在 N=10^5、T=10^18 的情况下也非常稳。快速幂内部的乘法全部在 mod 意义下进行，中间值不超过 MOD^2，用 long long 足够存，不会溢出。如果 T 再大，甚至超过 long long，那就需要用字符串读入再配合欧拉降幂，不过那是极少数情况了。
我还想提一个和初始数组大小有关的点：如果 N 很大，vector 的空间是可控的，没必要开普通数组。用 vector 的好处是不用手动管理内存，也不会因为数组开小了越界。如果你习惯用 C 风格数组，一定要看清题目里 N 的上限，开数组时留出余量。
5. 这道题带给我的启发
我最初看到“求和”题，第一反应是维护前缀和或者模拟，结果走了弯路。后来把操作矩阵拆成 J 和 I，一切才开始清晰起来。这个“把复杂矩阵幂化简成两个系数”的思路，对我后续刷其他线性递推题帮助很大。
最后再分享一个小技巧：遇到这种 T 巨大的轮换操作题，先不要急着写代码，试着在纸上算三轮、四轮，看每个数和自己初始值、总和的系数有没有规律。一旦发现 p 和 q 是分开迭代的，公式基本就到手了。信奥刷题打卡到第 3004 个，最大的体会就是：很多看似简单的题，卡住的不是代码，而是你愿不愿意停下来先推两步数学。
