# 编辑城镇与模拟币3：人均财富差与闭式公式

Codex（GPT-6）给出固定两户的最优性证明、闭式公式和实现。下面的推导只使用题目的搬家规则。

## 1. 结论

记 $k=p_1$ ，$l=p_2$ .若 $l=0$ ，答案为 $m_1$ .以下设 $l>0$ ，并记

$$
a=\frac{m_1}{k},\quad b=\frac{m_2}{l},\quad N=k+l,\quad r=\min(k,l),\quad t=\max(k,l).
$$

若 $a\ge b$ ，不编辑最优。否则令

$$
D=\left\lfloor\frac{(N+1)^2}{4}\right\rfloor,\qquad \rho=1-\frac ND.
$$

答案为

$$
W=\frac{k(m_1+m_2)}N+\frac{r^2}N(b-a)\rho^r.
$$

例如 $k=l=2,m_1=2,m_2=18$ 时，$\rho=1/3$ ，答案为 $10+8/9=98/9$ .

## 2. 两户的高低关系不会反转

固定位置A、B当前有 $s,N-s$ 人，人均财富分别为 $u,v$ .一人从A搬到B后，只要A仍非空，它的人均财富还是 $u$ ，而B变为

$$
v'=\frac{(N-s)v+u}{N-s+1}.
$$

因此差 $v-u$ 乘上 $(N-s)/(N-s+1)$ .一人从B搬到A则使差乘上 $s/(s+1)$ .这些因子在两户都保持非空时严格位于0和1之间。

若一户变空，全体居民已经合为一家，所有居民人均财富相等；此后任何搬家都保持这个均值。

所以两个位置的人均财富高低关系始终不变，差距只能缩小。这是固定两户可以简化的关键。

## 3. 选择最终位置

若 $a\ge b$ ，A初始不比B穷。目标最终在A且人数恢复为 $k$ 时，人均差不可能比初始更大；若最终在B，则目标处于较穷的一侧。两种情况都不能超过初始财富 $m_1$ .

以下设 $a<b$ .目标最终回到A时，最多得到全城均分份额 $k(m_1+m_2)/N$ .先将全体合并，再按身份拆开，可以达到这份财富。

若目标最终在B，两户必须交换全部成员。设最后人均差为初始差的 $F$ 倍。最终A有 $l$ 人、B有 $k$ 人，由财富守恒可得目标财富为

$$
W=\frac{k(m_1+m_2)}N+\frac{kl}N(b-a)F.
$$

因此只需最大化差距保留比例 $F$ .

## 4. 任意搬家策略的上界

先处理 $N\ge3$ ，并考虑全程两户非空的策略。令 $s$ 为A的人数，每次搬家让 $s$ 加一或减一。初始为 $k$ ，最终为 $l$ .

跨过人数边 $h\leftrightarrow h+1$ 往返一次，差距乘上

$$
\rho_h=\frac h{h+1}\frac{N-h-1}{N-h}
=1-\frac N{(h+1)(N-h)},\qquad 1\le h\le N-2.
$$

对每条边，将向上和向下的穿越次数配对。没有配对的穿越恰好组成从 $k$ 到 $l$ 的单调路径，其因子连乘为 $r/t$ .这由相邻分子分母约去得到：向上时为 $k/l$ ，向下时为 $l/k$ .

设总搬家次数为 $L$ .每位居民最终都要换位置，因此 $L\ge N$ .配对数为

$$
q=\frac{L-|k-l|}{2}\ge r.
$$

由于 $(h+1)+(N-h)=N+1$ ，两因子尽量接近时乘积最大，其最大值为 $D$ .故每个往返因子均不超过 $\rho$ ，且 $0<\rho<1$ ，从而

$$
F\le\frac rt\rho^q\le\frac rt\rho^r.
$$

经过空户的策略已经全体均分，不会超过这个上界对应的财富。

## 5. 上界可以达到

取 $h=\lfloor N/2\rfloor$ .它对应一条使 $(h+1)(N-h)=D$ 的人数边。

构造人数路线：先从 $k$ 单调走到 $h$ ，在 $h\to h+1\to h$ 上往返 $r$ 次，最后从 $h$ 单调走到 $l$ .由于 $h$ 位于 $k,l$ 之间，总步数恰为 $N$ .

每当A人数减少，就把一名尚未搬过的目标成员从A搬到B；每当A人数增加，就把一名尚未搬过的外部居民从B搬到A。整条路线恰好包含 $k$ 次减少和 $l$ 次增加，因此每一步都有人可搬，每个人只搬一次，最终两户交换全部成员。

差距比例恰为 $(r/t)\rho^r$ .代入上一节，并使用 $kl(r/t)=r^2$ ，得到所述公式。

若 $N=2$ ，则两户初始各一人。一次合并、一次拆开即可均分，$\rho=0$ ，同一公式仍成立。所有分支的最优值都能有限次达到。

## 6. 模运算与实现

先用64位整数比较 $m_1l$ 和 $m_2k$ ，确定是否需要编辑。不能比较模值，也不需要浮点数。

若 $N=2q$ ，则 $D=q(q+1)$ ；若 $N=2q+1$ ，则 $D=(q+1)^2$ .用64位整数计算 $D$ 和交叉乘积。

需要的分母因子为 $k,l,N$ 以及构成 $D$ 的两个整数。它们都严格小于 $P$ 且非零，因此在模 $P$ 下可逆；即使 $D>P$ ，它也不被 $P$ 整除。约分后的最优财富分母同样与 $P$ 互素。

用费马小定理求逆元、二进制快速幂求 $\rho^r$ .所有模乘法使用64位整数，并在连乘之间取模。初始交叉乘积最多为 $10^{15}$ ，也在64位范围内。

设每份存档最大初始人数为 $M$ .单份时间复杂度为 $O(\log P+\log M)$ ，额外空间为 $O(1)$ ；共 $T$ 份存档，时间为 $O(T(\log P+\log M))$ .

## 7. 两种计算方式

[标准程序](std.cpp)直接计算闭式公式。另有[最优搬家路线的仿射变换解法](solution-alternative-affine.zh.md)及其[程序](alternative-affine.cpp)：先构造已证明最优的人数路线，再批量计算每一段的家庭财富。两者共享最优路线证明，计算过程不同，均为常数空间、对数时间，均通过完整数据。

仿射方案可以直接对应实际搬家过程；闭式公式便于独立计算最终答案，选作标准程序。小规模另使用精确分数的全状态最短路核验，其用途见[测试说明](tests/README.md)。