题解：P16681 玩具

· · 题解

题解：P16681 玩具

题意

有一个由无数圆形组成的玩具，其中每个圆形都能填一个小写字母，但是相邻两个字母不能都是元音（辅音字母 21 个，元音字母 5 个），求有多少种方法。

由于数字太大，所以 \bmod\ 998244353 即可。

对于原题目描述，玩具形状，请返回 problem。

思路

如果不知道下列算法，建议先查对应资料。

设一共有 z 个小写字母（实际为 26 个），每一列有 n 个圆形（实际为 341799 个）。

Lv.1 暴力

首先，可以暴力枚举所有方法，然后计算合法方式数量。

但是时间复杂度 O(z^n)，考虑到玩具的实际样子，最多运行约 2.5\times 10^{1450909} 次，不可能过题。

Lv.2 动态规划

那么，可以发现除了相邻两个圆形之间不能都是韵母外没有其他限制，因此可以记录必要的状态即可。

那么，可以先建立三维数组 dp1，dp1_{i,j,k} 代表在只考虑第一列圆形的前 i 个时在确定第 1 个圆形和第 i 个圆形分别是否为韵母时的情况。

关于为什么要存第一个位置是否为韵母，你一会就知到了。

首先，先给仅有一个圆形时的情况赋初值。 :::info[提示]

dp1_{1,0,0} \gets 21 dp1_{1,1,1} \gets 5

::: 然后，从小到大枚举所有 i，每一次计算能产生多少的计算方法，当然别忘了不能连续两个位置都是韵母、乘以字符的选择方式数以及模值。 :::info[提示] 注：此处没有取模运算，实际编程时需加上（包括后面所有提示）。

dp1_{i,0,0}\gets (dp1_{i-1,0,0}+dp1_{i-1,0,1})\times 21 dp1_{i,0,1}\gets dp1_{i-1,0,0}\times 5 dp1_{i,1,0}\gets (dp1_{i-1,1,0}+dp1_{i-1,1,1})\times 21 dp1_{i,1,1}\gets dp1_{i-1,1,0}\times 5

::: 接下来，建立二维数组 dp2，dp2_{i,j} 代表第二列的第一个位置以及最后一个位置是否为韵母，这下你知道为什么要一直记录第一个位置是否为韵母了吧。

按照合法的组合方式得到他们的结果。 :::info[提示]

dp2_{0,0}\gets(dp1_{n,0,0}+dp1_{n,0,1}+dp1_{n,1,0}+dp1_{n,1,1})\times 441 dp2_{0,1}\gets(dp1_{n,0,0}+dp1_{n,1,0})\times 105 dp2_{1,0}\gets(dp1_{n,0,0}+dp1_{n,0,1})\times 105 dp2_{1,1}\gets dp1_{n,0,0}\times 25

::: 接着新建四维数组 dp3，dp3_{i,j,k,l} 代表对于当有前两列的内容和第三列前 i 个，且已知第三列第一个圆形、第三列第 i 个圆形和第二列另一边的圆形的字母分别是否为韵母时的组合数。

首先先不考虑冲突情况，先将 dp3_{1,i,j,k} 的所有情况记录，然后在进行与 dp1 几乎一样的操作（只是第二列另一边的圆形的字母是否为韵母分开计算，不冲突，且为了不占篇幅，第三列中间的转换公式就不写了）。 :::info[提示]

dp3_{1,0,0,0}\gets (dp2_{0,0}+dp2_{1,0})\times 21 dp3_{1,1,1,0}\gets dp2_{0,0}\times 5 dp3_{1,0,0,1}\gets (dp2_{0,1}+dp2_{1,1})\times 21 dp3_{1,1,1,1}\gets dp2_{0,1}\times 5

::: 但是，这时你可能好奇为什么要记录第二列最后一个圆形是否为韵母，因为你会发现 dp3_{n,0,1,1} 和 dp3_{n,1,1,1} 是不合法的，可以将这两个值赋值为 0 或者在后面操作值时踢出这两个数。

接着新建二维数组 dp4，作用和 dp2 几乎一模一样，只是换到了第四列而已，而计算也和 dp2 几乎一样，只需将 dp3 的第四维的所有值的和加起来再套用即可，并且别忘了如果没有赋值为 0，那么要将刚才说的所有违禁情况删掉。

最后建立四维数组 dp5，作用、计算方式和 dp3 几乎一模一样，只是换到了第五列。

最终，答案为 dp5_{n,0,0,0}+dp5_{n,0,0,1}+dp5_{n,0,1,0}+dp5_{n,1,0,0}+dp5_{n,1,0,1}+dp5_{n,1,1,0}。

时间复杂度 O(n)，最多运行 341799 次，即使常数有点大，不过也能过，嫌时间长的的可以在本地运行结果，直接输出。 :::warning[警告] 本题解中在计算 dp4_{0,0} 时的最大可能出现值约为 3.5\times 10^{12}，即使在求和后就模值一下，第二次运算时也会最大到 4.4\times 10^11，请使用 long long（假如不踢出不合法情况，如果巧合 int 就能过请私信）。 ::: 我的 AC 记录。