前向批量平均¶

Codex（GPT-6）给出本题中的下三角矩阵批量展开、程序与验证。程序与主解使用同一已证明最优的逐人策略，但直接维护目标成员财富，不计算逆序系数尾和。

一个居民对应一个线性变换¶

目标财富向量按较富到较穷记为 \(x_0,\ldots,x_{k-1}\) .当前家庭的每人初始财富为 \(v\) .减去这个常数，记 \(y_i=x_i-v\) .让一名外部居民依次与全部目标平均，相当于

\[ y'_i=\sum_{j=0}^{i}2^{-(i-j+1)}y_j. \]

令 \(L\) 为向下移一格的矩阵，即 \((Ly)_i=y_{i-1}\) 且第0项为0。单次更新矩阵为 \(B=\tfrac12(I-L/2)^{-1}\) .由于 \(L^k=0\) ，处理 \(p\) 名同均值居民时，负二项式展开是有限的精确等式：

\[ B^p=2^{-p}\sum_{d=0}^{k-1}\binom{p+d-1}{d}2^{-d}L^d. \]

因此整个家庭一次更新为

\[ x'_i=v+2^{-p}\sum_{j=0}^{i}\binom{p+i-j-1}{i-j}2^{-(i-j)}(x_j-v). \]

按人均财富递增处理所有比初始目标均值更富的家庭。每次先算卷积系数，再用旧向量计算完整的新向量，最后交换数组；不能在正向循环中覆盖还要使用的旧值。最终将 \(k\) 项求和即可。

每个矩阵 \(B\) 精确表示一位外部居民的全部两人平均，\(B^p\) 精确表示同一家庭所有居民的连续操作。家庭顺序和跳过条件与主解中的最优策略一致，所以输出同一个最优值。最终合并目标成员只改变各人的均值，不改变其总财富。

卷积系数用相邻二项式递推计算，分母至多 \(k-1\) .人均值的模逆和 \(2^{-p}\) 使用快速幂，不需要长度为 \(M\) 的表。实际均值的大小仍用交叉乘法比较。没有更富者时，目标总财富保持为 \(m_1\) .

记 \(M=\max_i p_i\)、模数为 \(P\) .排序耗时 \(O(n\log n)\) ，总时间为 \(O(n\log n+n(k^2+\log P+\log M))\) ，空间 \(O(n+k)\) .

本方法省去标准程序的 \(O(M)\) 逆元和负幂表，代价是每个家庭的二次卷积及快速幂。它提供直接追踪目标成员财富的另一种实现，数值操作全为精确模运算。是否满足按标准程序校准的时限，以及实际空间差异，见完整测量。