P8562 十二重骗分法（Cheating XII）

· · 题解

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

第一部分 求平方根

测试点 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 了）