GitHub 源文件 Markdown English

编辑城镇与模拟币5：题解

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}\) .按列遍历时，一个外部居民依次与目标成员从富到穷平均；按行遍历时，一个目标成员依次访问所有外部居民。两种遍历遵守相同的依赖关系，得到相同结果：每格只涉及该行的目标和该列的外部居民，不同行且不同列的就绪操作互不影响。

在固定位置内达到上界

先将初始人均财富相同的较富外部家庭合并。搬家两端均值相同，因此这些居民的个人财富保持不变，最终只保留 \(g\) 个较富的源家庭。

将所有不比目标富的外部家庭合为一个收集家庭；这些人不参与网格，他们合并后的均值仍不超过 \(a\) ，不会改变上界。若没有这些居民，就留出一个空位置作为收集家庭。再把目标成员拆成 \(k\) 个单人家庭。

总共需要 \(k+g+1\) 个位置。合并只会释放位置，拆出目标成员前已有足够空位；题目的位置数保证使这一准备过程始终可行，即使初始没有空家庭。

按均值从低到高处理较富源家庭。每次取出一人，依次访问所有目标单人家庭，再搬入收集家庭。各次访问恰好平均两人，源家庭剩余居民仍保留该组初始均值。目标成员按网格行号访问，它们的当前财富从高到低排列。收集家庭不再参与操作。

全部外部居民处理完后，将目标成员合为一家。其总财富不变，恰好是网格给出的上界，且始终使用已有位置。

按财富种类计算贡献

直接展开所有居民不可行，总人口可以接近 \(10^{12}\) .从所有财富中减去 \(a\) ，使目标初值为0。若某个外部居民之后还有 \(s\) 个外部居民，它对最终目标总财富的系数为

\[ w_s=\sum_{i=1}^k\binom{s+i-1}{i-1}2^{-(s+i)}. \]

这是网格路径计数：从该列上边界进入第 \(i\) 行、再到最后一列，共有 \(\binom{s+i-1}{i-1}\) 条路径，每条经过 \(s+i\) 次取半。

定义尾和 \(F(s)=\sum_{t=s}^{\infty}w_t\) ，可得

\[ F(0)=k,\qquad F(s)=2^{-s}\sum_{j=0}^{k-1}(k-j)\binom{s+j-1}{j}2^{-j}\quad(s\ge1). \]

证明这个有限式时，固定 \(i\) .公平硬币第 \(i\) 次正面前恰好出现 \(t\) 次反面的概率是 \(\binom{t+i-1}{i-1}2^{-(t+i)}\) .至少出现 \(s\) 次反面，等价于第 \(s\) 次反面前只有 \(j<i\) 次正面，对这些 \(j\) 求和即可。再对 \(i\) 求和，每个 \(j\) 被计算 \(k-j\) 次。该概率解释只用来推导有理数恒等式，程序使用有限式取模。

将较富外部居民按初始人均财富分组，从高到低扫描。设已处理 \(s\) 人，当前组有 \(c\) 人、均值 \(v\) ，则该组贡献为

\[ (v-a)\bigl(F(s)-F(s+c)\bigr). \]

从 \(m_1\) 开始累加贡献。每个尾和只用 \(O(k)\) 次运算，用下面的递推计算二项式：

\[ \binom{s+j-1}{j}=\binom{s+j-2}{j-1}\frac{s+j-1}{j}. \]

精确分组与跨模数人数

读入时先用64位交叉乘法判断 \(m_i k>m_1p_i\) ，再与至多三个已有组比较 \(m_i p_{\mathrm{rep}}=m_{\mathrm{rep}}p_i\) .这样既不需要排序百万条输入，也不会把不同有理数误认为相等。

每组保存总人数，以及一个初始家庭的 \(p_{\mathrm{rep}},m_{\mathrm{rep}}\) .计算组均值时使用 \(m_{\mathrm{rep}}/p_{\mathrm{rep}}\) ；不要用合并后总人数求逆，它可能恰好是 \(P\) 的倍数。初始人数至多一百万，因此代表家庭的人数可以求逆。

总人数使用64位整数，指数 \(s\) 也不截断。二项式递推只除以 \(1,\ldots,k-1<P\) ，即使 \(s\ge P\) 仍然有效。相乘前先将 \(s+j-1\) 对 \(P\) 取模，避免64位乘法溢出。维护 \(2^{-s}\) 时，每组乘以快速幂得到的 \(2^{-c}\) .

达到上界的策略只让目标个人财富经历初始人数作分母以及两人平均；最终合并不改变目标总财富，所以答案分母与 \(P\) 互素。

复杂度、方案选择与检验

设较富外部居民总数为 \(Q\) .分组时间 \(O(n(g+1))\) ，计算时间 \(O(k+g(k+\log P+\log(Q+1)))\) ，空间 \(O(k+g)\) ；本题 \(g\le3,k\le20\) ，主要开销为读取输入。标准程序使用这个尾和方案。

前向卷积逐组更新每个目标成员，组内计算为 \(O(k^2)\) ；它同样通过完整范围，保留为另一种计算方法。两份程序共用最优性证明，但公式方向不同。

小输入使用精确 Fraction 网格；大输入使用从单人平均直接建立的矩阵和通用快速幂核对。另逐次模拟合法搬家，覆盖初始没有空位、位置数恰好足够、相等分数以及总人数跨越模数。测试说明与性能记录。