题解 | #被遗忘的书籍#: 拒接间接求答案——dp值就是答案

C题题解都是间接求答案，即求出非法可能数，再从所有可能中减去，我补充一个直接求答案的DP方法：

1. dp下标

表示：当前枚举第i个字母，第j种状态。

2. dp状态

这里列出所有状态的可能：

• : 从 到 中 不包含txt, 且结尾不为t;
• : 从 到 中 不包含txt, 且结尾为t;
• : 从 到 中 不包含txt, 且结尾为tx;
• : 从 到 中任意地方包含 txt.

【补充】

3. dp转移方程

根据上述四种状态，可以给出状态转移方程。

• :
  • 前一个状态为, 在后面跟任意一个不为t字母即可, ;
  • 前一个状态为, 在后面跟任意一个不为t或者e（如果是e，就变成了以te结尾）字母即可, ;
  • 前一个状态为, 在后面跟任意一个不为t字母即可, ;
  • 前一个状态为, 则无法转移到当前状态；
  • + + .
• :
  • 前一个状态为 或 ，只需在后面跟一个t字母即可, ;
  • 前一个状态为 ， 此时无法转移到当前状态，因为当后面接一个t时，就变成了tet结尾；
  • + .
• :
  • 当前状态只能由 后面接一个字母e转移而来；
  • .
• :
  • 前一个状态为 ，后面只需跟一个t即可，;
  • 前一个状态为 ，此时后面接任何字母均可，;
  • + .

【补充】

这牛客的公式有问题，在行内公式的+不显示，所以上面公式的+都是拼接的，希望可以修一下bug.

4. dp初始条件

• 选择 作为初始条件，此时对于 长度的字符串，其为1种满足 的状态。
• 选择 作为初始条件，此时对于 长度的字符串，有25种满足 的状态， 有1种满足 的状态，其余状态则为 0。

【补充】

5. 最终结果

最终对任意长度 ， 即是我们需要的答案，而不用再去算幂做差。

6. 代码

下面提供 Python 代码

dp = [[0]*4 for _ in range(2*10**5 + 1)]
dp[0][0] = 1
m = 998244353

for i in range(1, 2*10**5 + 1):
    d = dp[i-1]
    dp[i][0] = (25 * d[0] + 24 * d[1] + 25 * d[2]) % m
    dp[i][1] = (d[0] + d[1]) % m
    dp[i][2] = d[1]
    dp[i][3] = (d[2] + 26 * d[3]) % m

for _ in range(int(input())):
    print(dp[int(input())][-1])