GitHub 源文件 Markdown English

编辑城镇与模拟币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\) ，因此下一行起点正确。

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

该构造在有限次编辑后达到上界，所以本题确实求得最大值。实际算法无需执行可能多达 \(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\) 是较富的外部居民数量，目标人数可以达到一百万。标准程序实现上述递推。

检验

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

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