# 编辑城镇与模拟币3：按最优路线计算财富

Codex（GPT-6）给出最优搬家路线的批量仿射计算。最优路线及上界证明见[主解](solution.zh.md)，本方案直接计算这条路线的家庭财富，不代入最终闭式公式。

## 路线与批量搬家

沿用 $k,l,N,r$ ，记全城财富为 $S=m_1+m_2$ ，A当前财富为 $x$ .空户或目标初始人均财富较高时仍直接返回 $m_1$ .

否则取 $h=\lfloor N/2\rfloor$ ，执行 $k\to h$、$r$ 次 $h\to h+1\to h$、$h\to l$ 的人数路线。主解已经证明它合法且最优，最终目标全部在B。

一段单调路线令A人数从 $s$ 变到 $t$ ：

- 若 $t<s$ ，连续从A搬出居民，A的人均财富不变，所以 $x'=xt/s$ .
- 若 $t>s$ ，连续从B搬出居民，B的人均财富不变，所以 $x'=S-(S-x)(N-t)/(N-s)$ .
- 若 $s=t$ ，财富不变。

两段单调路线各用常数次模运算完成。

## 重复往返

从A有 $h$ 人开始，先把一人从B搬到A，再把一人从A搬回B。A财富依次变为

$$
x'=x+\frac{S-x}{N-h},\qquad
x''=\frac h{h+1}x'=\alpha x+\beta,
$$

其中

$$
\alpha=\frac h{h+1}\left(1-\frac1{N-h}\right),\qquad
\beta=\frac{hS}{(h+1)(N-h)}.
$$

对仿射函数 $f(x)=\alpha x+\beta$ 做二进制快速幂。平方后的系数为 $(\alpha^2,\alpha\beta+\beta)$ ；当指数当前位为1时，把对应函数应用到当前财富。

随后执行最后的单调路线。此时A全是外部居民，B全是目标成员，答案为 $S-x$ .

## 正确性、复杂度与适用范围

每个批量转移都等价于对应的逐人搬家；仿射快速幂恰好重复 $r$ 次往返。因此程序精确计算主解已经证明最优的路线，输出同一最大财富。

所有分母均为正整数且小于模数，模运算合法；$N=2$ 时往返会经过空户，但这两步仍合法，公式没有除以零。

设最大初始人数为 $M$ .每份存档时间为 $O(\log P+\log M)$ ，额外空间 $O(1)$ .本方案支持完整范围，与闭式公式方案并列提供；它更直接地对应搬家过程，两者实测均通过参考时限。代码见[alternative-affine.cpp](alternative-affine.cpp)。