# 编辑城镇与模拟币4：题解

Codex（GPT-6）给出固定位置内的可达构造、最优性证明、批量计算公式、实现和验证。

## 个人财富与平均网格

记 $k=p_1$ 、$a=m_1/k$ .将居民的个人财富定义为所在家庭的人均财富。搬走一人不会改变源家庭剩余居民的人均财富；搬入另一个家庭，恰好将搬入者与目的家庭全体成员的个人财富取平均。因此，每次合法搬家都是一组人的完全平均。

先放宽家庭位置数，求所有平均操作都不能超过的上界，再给出在本题固定位置数内达到上界的构造。

## 任意编辑都不能超过的上界

这一段允许目标成员的当前财富不同，以便把同一结论用于任何中间状态。

将所有人按财富非降排序，目标标为 $T$ ，外部标为 $O$ .只要相邻标签为 $TO$ ，就将两人的财富平均，并交换他们在排序表中的位置。两人现在同样富，列表仍然有序。重复直到全部 $O$ 位于全部 $T$ 之前，将此时的目标财富总和记为 $\Phi$ .

**操作顺序不影响结果。** 每步消除一个标签逆序。两个同时可操作的 $TO$ 不可能重叠，它们作用于不同坐标，可以交换执行顺序。对逆序数归纳，所有执行顺序得到同一个最终财富向量。

**每一步都不减少目标财富。** 被平均的目标成员不比外部成员富。因此 $\Phi$ 不小于当前目标财富总和，而且在位置数不限的模型中，这个值可用有限步达到。

**任意两人平均都不增加 $\Phi$ .** 固定财富排序后，所有操作都是固定的相邻平均矩阵，$\Phi$ 是初始财富的线性函数。结束时目标总和对有序坐标的系数是

$$0,0,\ldots,0,1,1,\ldots,1.$$

倒推操作时，每步同样把相邻两个系数平均，所以系数始终非降。也就是说，较富坐标的系数不小于较穷坐标。

让任意两人的财富 $x<y$ 连续向均值靠近。在排序固定的一段中，设对应系数为 $c_x\le c_y$ ，向较穷者转移 $\delta$ 会使势函数变化

$$\delta(c_x-c_y)\le0.$$

排序发生变化时，$\Phi$ 连续：两个同类人员在相等财富处交换没有影响；异类人员在相等处可以先执行那次不改变财富的 $TO$ 操作，得到另一侧的问题。整个平均过程经过有限个排序区间，因此 $\Phi$ 不增。

**多人平均也不增加 $\Phi$ .** 一组人的完全平均可由该组内反复的两人平均逼近，连续性将不增结论推广到这个极限。这仅用于证明上界；达到上界的策略本身只有有限步。

于是任意编辑后的目标财富不超过当时的 $\Phi$ ，后者又不超过初始 $\Phi$ .前述相邻策略恰好达到它，最优性得证。

## 写成递推

初始所有目标成员都拥有 $a$ .不比 $a$ 富的外部居民无需参与。将其余 $r$ 人的初始财富排为 $v_1\le\cdots\le v_r$ .

上述相邻平均可以写成网格：

$$x_{i,0}=a,\qquad x_{0,j}=v_j,\qquad x_{i,j}=\frac{x_{i-1,j}+x_{i,j-1}}2.$$

最优值为 $\sum_{i=1}^k x_{i,r}$ .按列遍历时，一个外部居民依次与目标成员从富到穷平均；按行遍历时，一个目标成员依次访问所有外部居民。两种遍历遵守相同的依赖关系，得到相同结果：每格只涉及该行的目标和该列的外部居民，不同行且不同列的就绪操作互不影响。

## 一个空位置为什么足够

外部居民初始各自住在单人家庭中。保留目标成员的源家庭，再选一个初始空位置作为收集家庭。

依次取出一个目标成员，让他按初始财富从低到高访问所有较富外部居民的家庭，最后搬入收集家庭。每次访问时恰有两人；目标成员离开后，外部居民又单独居住。还留在源家庭的目标成员仍各自拥有 $a$ ，因此下一行起点正确。

进入收集家庭的目标成员不再参与平均，内部混合只改变个人分配，不改变他们的总财富。这个过程正是逐行计算上述网格，最后全部目标成员在收集家庭团聚。即使有很多目标成员，也只需源家庭、外部居民的单人家庭和一个收集家庭，始终不增加位置。

![两行访问后目标成员在D团聚](assets/example.svg)

该构造在有限次编辑后达到上界，所以本题确实求得最大值。实际算法无需执行可能多达 $k(r+1)$ 次的搬家。

## 批量计算所有目标成员

令外部居民的初始超额财富为 $z_j=v_j-a$ ，按非降序组成列向量 $z$ .一位从超额财富0出发的目标成员访问全部外部居民后，外部超额财富变为 $Bz$ ，其中

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

$L$ 是向下移动一格的 $r\times r$ 矩阵。访问后的第 $i$ 位外部居民财富满足 $y_i=(y_{i-1}+z_i)/2$ ，且 $y_0=0$ ，故该矩阵表达式成立。

全部 $k$ 位目标成员处理完后，外部超额财富为 $B^kz$ .由于 $L^r=0$ ，二项式展开是有限的：

$$B^k=\sum_{d=0}^{r-1}c_d L^d,\qquad c_d=2^{-(k+d)}\binom{k+d-1}{d}.$$

定义 $C_d=\sum_{t=0}^d c_t$ .第 $j$ 位外部居民的初始超额财富在最终外部总财富中的系数为 $C_{r-j}$ .由财富守恒，目标家庭的最大财富为

$$W=m_1+\sum_{j=1}^r(v_j-a)(1-C_{r-j}).$$

从最大的外部财富向最小的扫描，同时递推

$$c_0=2^{-k},\qquad c_d=c_{d-1}\frac{k+d-1}{2d}\quad(d\ge1),$$

即可在排序后用线性时间计算答案。若 $r=0$ ，直接输出 $m_1$ .

## 模运算与复杂度

所有大小比较在整数域进行：判断外部财富 $v$ 是否较大，使用 $vk>m_1$ .乘积至多 $10^{15}$ ，应使用64位整数。不要比较取模后的财富。

预处理 $1,\ldots,r$ 的逆元，快速幂求 $k^{-1}$ 与 $2^{-k}$ .本题 $k,r<P$ ，且 $k+r-1<P$ ；递推中的除数均可逆。构造中涉及目标初始分母 $k$ 和反复除以2，最大财富的分母与 $P$ 互素。

时间 $O(n+r\log r+r+\log P+\log k)$ ，空间 $O(r)$ .这里 $r$ 是较富的外部居民数量，目标人数可以达到一百万。[标准程序](std.cpp)实现上述递推。

## 检验

小数据与精确 Fraction 网格比较，并逐次模拟固定位置内的合法搬家、检查财富守恒和目标身份。大目标人数的小外部集合使用通用矩阵快速幂；财富种类少的大输入使用按列推导的尾和公式；另覆盖百万不同财富和无收益输入。

一份一般大输入以同一系数恒等式的阶乘实现核对，不能视为独立最优性证明。正确性依据上面的上界与可达构造。正式计时见[性能记录](../../../docs/benchmark-R42.json)，复现方法见[测试说明](tests/README.md)。