编辑城镇与模拟币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\) .

固定位置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之间。

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

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

若 \(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\) .

先处理 \(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. \]

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

取 \(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\) ，同一公式仍成立。所有分支的最优值都能有限次达到。

先用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))\) .

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

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