自动搬运

查看原文

来自洛谷，原作者为

	NaCly_Fish 北海虽赊，扶摇可接。

搬运于2025-08-24 22:40:10，当前版本为作者最后更新于2022-10-10 20:32:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

整个题目分为四部分内容讲解。

第一部分 求平方根

测试点 1：
可以发现输入的规律是 $5444 \cdots 42888 \cdots$，但是最后有一段乱掉的内容。发现前半部分 4 的位数，比在中间的 2 后面的位数少一位。
尝试小数据可以发现如 $2333333^2=5444442888889$ 这样的规律（可以用线性递推数列来证明）。而这里的输入后面虽然稍大，但其平方根下取整后依然是 $2333 \cdots$。

测试点 2:
大家一定知道如 $111111^2=12345654321$ 这样的结论吧！观察输入数据，发现整体是比较对称的，只是最后一位看起来应该是 4，但实际是 1。同样是按照规律，答案就是若干个 $200000$ 的拼接，最后再接个 1。证明和上一个点时类似的。

---

第二部分 二分图完美匹配计数

测试点 3：

左边的 1 号点只能匹配右边的 1 号；由此左边的 2 号也只能连接右边的 2 号，以此类推，只有一种方案。

测试点 4：

看不出什么明显的规律，但如果你的屏幕够长，很容易发现输入数据像条形图一样。 若尝试打出邻接矩阵，就很明显了：整个图分成了许多连通块，每个连通块中左边的点都连接了所有右侧的点（即完全二分图）。那么一边有 $n$ 个点的这种连通块，答案显然为 $n!$，把每个连通块的答案乘起来即可。

测试点 5：

左侧的 $i$ 号点（从 0 开始计）会连接编号为 $(i+k) \bmod 60000 \ \ k \in [0,4]$ 的右侧点。可以按照这个规律，设有 $n$ 个点，打一些小数据的表。可以猜测答案满足一个常系数线性递推，用 BM 算法找出递推式，暴力计算即可。

如果对 dp 加一些优化，大概也是能在可接受的时间内跑出答案的。当然你也可以在 OEIS 上找到这个数列。

测试点 6：

首先每个点的度数都不超过 4。再稍作分析，就能发现这是一个 $n \times m$ 的网格图，再交错地黑白染色，使每个格子周围的四个都与其颜色不同。最后在相邻的格子之间连边，就是题目中的情况。

手玩一下小数据的方案，发现实际上所求就是用 $1\times 2$ 的骨牌铺满 $n \times m$ 的网格的方案数。如果你对《具体数学》的内容记得比较清楚，你一定能找到这样一个公式（证明比较难，我也不会）：

$$2^{nm/2}\prod_{j=1}^m \prod_{k=1}^n\left(x^2\cos^2 \frac{j \pi}{m+1}+y^2 \cos^2\frac{k \pi}{n+1} \right)^{1/4} $$

它的 $x^py^q$ 项系数就表示用 $p$ 个竖骨牌和 $q$ 个横骨牌铺满的方案数。只需要令 $x=y=1$ 就是我们想要的答案了。

将 $\cos$ 函数用单位根来表示，就得到答案为：

$$\prod_{j=1}^m \prod_{k=1}^n (\omega_{m+1}^j + \omega_{m+1}^{-j}+\omega_{n+1}^k +\omega_{n+1}^{-k}+4)^{1/4} $$

在此题中 $m=511$，$n=118$，满足 $(m+1)|p$ 且 $(n+1)|p$，可以直接用原根来计算单位根。那么主要问题就是怎么开四次根。考虑到 $n+1$ 是奇数，$k$ 和 $n+1-k$ 的乘积项必然相同；但 $m$ 是奇数，$j= \lceil m/2 \rceil$ 时这一项多了出来，我们将答案写成：

$$\left(\prod_{j=1}^{\lfloor m/2 \rfloor}\prod_{k=1}^{n/2}(\omega_{m+1}^j + \omega_{m+1}^{-j}+\omega_{n+1}^k +\omega_{n+1}^{-k}+4)\right) \prod_{k=1}^{n/2}(\omega_{n+1}^k+\omega_{n+1}^{-k}+2)^{1/2} $$

而后面那段乘积项是 $\omega_{n+1}^{k/2}+\omega_{n+1}^{-k/2}$，可以直接计算；当然也容易证明整体就是 $1$，直接忽略掉就行。然后就能以 $\Theta(nm)$ 的时间复杂度计算。对于更一般的情况，也有高效的做法，这里就不说了（

---

第三部分 生命游戏迭代预测

首先，这玩意手动模拟很难，建议写个小程序来模拟；或者直接找现成的可视化工具，把输入丢进去就好。

测试点 7：.

输入量不小，但运行一下就能发现，其细胞数是周期变化的。这就是典型的「飞船」模型，整体向着固定方向移动，而内部的形态呈周期变化。

测试点 8：

这次的输入很少，却能快速地增长，并铺满整个平面。下图为迭代 50 次后的图案：

四角向外移动的部分的形状，是以 $4$ 为周期变化；再结合其增长速度显然为平方级，可以猜测：在第 $4t$ 次迭代后的细胞数，关于 $t$ 是个二次多项式。那就很简单了，简单插值可以得到 $4t \ \ (t \ge 1)$ 代后的细胞数为 $195+38t+4t^2$，注意需要高精度运算。

测试点 9：

现在需要对图案进行深入分析。首先可以看到有一个「飞船」，以很小的匀速度向左上移动；还有一个「滑翔机」，沿左上和右下方向往返移动。当「滑翔机」触及右下角的部分时，就会有一个「滑翔机」向右上飞去。

注：所谓滑翔机，就是这样的结构：

显然，这也是一个可以无限增长的形态，但是增长得很慢，有多慢呢？假设向左上的大飞船速度为 $u$，滑翔机速度为 $v$，飞船初始到右下的距离为 $S_0$，则第 $n$ 次往返所需时间 $T_n$，与返回后飞船到右下的距离 $S_n$ 为：

$$T_n = \frac{S_{n-1}}{v}+\frac{S_{n-1}}{v-u}\left( 1+ \frac{u}{v}\right) = \frac{2S_{n-1}}{v-u} $$$$S_n=S_{n-1}+T_n u$$

简单代换可以得到：

$$S_n = \frac{v+u}{v-u}S_{n-1}$$

这就证明了细胞数是呈对数增长的。进一步分析，大飞船的速度为每 $96$ 代 $8$ 格，而滑翔机为每 $4$ 代 $1$ 格（横向和纵向移动相同距离），即 $u=1/12$，$v=1/4$，$S_n=2S_{n-1}$，每次往返所需时间翻倍。

由此合理推断：取合适的 $a$，在 $a\times 2^n$ 代时，细胞数为 $5n+b$。对于任意情况求解比较困难，这里给出：在 $a=960$ 时有 $b=376$。这个结果可以根据其它部分的周期来发现。而输入的迭代次数是 $960$ 的倍数，除掉之后刚好又是 $2$ 的整数幂。

最后推荐一个整合了许多相关资料的网站：Life Wiki。

---

第四部分 图染色计数

测试点 10：

一眼发现这个图有 $n$ 个点和 $n-1$ 条边，再验证一下这就是一棵树。我们随便选一个点开始染色，有 $k$ 种选择方式；与其相邻的点都有 $k-1$ 种方案，于是答案就是 $k(k-1)^{n-1}$。

测试点 11：

直接看不出什么性质，尝试打出邻接矩阵来，就可以发现有 $C=233$ 个点与之间的边形成了团，即它们的颜色必须两两不同。而剩下的点之间没有连边，都连向了那个团中的点。考虑先给团染色，方案数为 $k^{\underline C}$；剩下的点若度数为 $d$，只有 $k-d$ 种颜色可选，全部乘起来即可。

测试点 12：

也是个比较稠密的图，可以参考上一个测试点的方法，观察邻接矩阵发现：两个点之间有边相连，当且仅当它们模 $17$ 的结果不同。于是整个图可以分为 $17$ 个部分，每部分节点数相同；从中选出一个点，都要和其它部分中所有点不同色。

那么可以预见到这样一种计数方法：给每个部分一个可用、且必须都用到的颜色集合，集合之间没有交集。枚举将要出现的总颜色数 $c$，可以得到答案计算式：

$$\sum_{c=0}^k \binom kc \sum_{i_1+\cdots+i_{17}=c}\binom{c}{i_1,\cdots,i_{17}} \prod_{j=1}^{17}f(i_j) $$

其中的 $n$ 表示每一部分的节点数；$f(i)$ 表示给 $n$ 个点都涂色，有 $i$ 种颜色可用，且每种颜色都要用到的方案数。这个和第二类 Stirling 数很像，显然有

$$f(i)=\begin{Bmatrix}n \\ i \end{Bmatrix}i!$$

于是答案可以写为

$$\sum_{c=0}^k \binom kc c! [x^c]\left( \sum_{i=1}^n \begin{Bmatrix}n \\ i \end{Bmatrix} x^i\right)^{17} $$

可以直接 $\Theta(n^2)$ 计算，注意 $c$ 只需取到 $17n$ 即可。

---

至于最终的答案，都很容易计算，这里就不给出了。（而且也有人通过 WA 信息套取数据 AC 了）