# 前向批量平均

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

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

目标财富向量按较富到较穷记为 $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)$ 逆元和负幂表，代价是每个家庭的二次卷积及快速幂。它提供直接追踪目标成员财富的另一种实现，数值操作全为精确模运算。是否满足按标准程序校准的时限，以及实际空间差异，见[完整测量](../../../docs/benchmark-R40.json)。