# 编辑城镇与模拟币5：前向批量平均

Codex（GPT-6）给出本替代方案。它与[主解](solution.zh.md)使用相同的固定位置构造和最优性证明，直接维护每名目标成员的财富。[程序](alternative-forward.cpp)使用公共输入与模运算工具 [wealth.hpp](wealth.hpp)。

## 一组居民的作用

按初始均值从低到高处理较富的外部居民组。设当前组均值为 $v$ 、人数为 $c$ ，目标财富为列向量 $x$ .减去 $v$ 后，单个外部居民从0出发依次与目标平均，故偏差向量被矩阵

$$B=\frac12(I-L/2)^{-1}$$

作用一次；这里 $L$ 是 $k\times k$ 的向下移动矩阵。重复 $c$ 次得到 $B^c$ ，其下三角卷积核为

$$h_0=2^{-c},\qquad h_d=h_{d-1}\frac{c+d-1}{2d}\quad(1\le d<k).$$

于是

$$x_i'=v+\sum_{j=1}^i h_{i-j}(x_j-v).$$

一组只需 $O(k^2)$ 运算，无需枚举居民。用两个数组保存前后向量，避免在卷积中覆盖旧值。全部组处理完后，输出目标向量各项之和。

## 实现边界与复杂度

组均值由一个初始代表家庭计算，其人数小于 $P$ .总人数 $c$ 可能超过 $P$ ，仍使用完整64位数作幂指数；递推乘法前先对 $c+d-1$ 取模，只对 $d<P$ 求逆。

分组时间为 $O(n(g+1))$ ，计算时间为 $O(k+g(k^2+\log P+\log(Q+1)))$ ，空间为 $O(k+g)$ .本题 $k\le20,g\le3$ ，该实现通过全部正式文件。主解的每组计算为线性，作为标准方案；此实现用于展示逐人平均的另一种批量计算方式。

大数据与通用矩阵快速幂比较，小数据与精确 Fraction 平均网格比较。[测试说明](tests/README.md)和[性能记录](../../../docs/benchmark-R42.json)。