禁用子串 题解

思路

所有禁用串的长度都不超过 $6$。在已经构造出的字符串合法时，追加一个字符后，新的非法子串一定以新字符结尾。因此，只需记住当前字符串最后至多 $5$ 个字符，就能判断下一次追加是否合法。

当长度达到 $5$ 后，状态可以统一表示为一个五位二进制数，共 $32$ 种。对每个状态分别尝试追加 a 和 b，若所得六字符窗口的某个后缀等于禁用串，就舍弃这条转移；否则转移到新的五字符后缀。

由此得到一个 $32\times32$ 的转移矩阵。由于 $N$ 很大，使用矩阵快速幂计算剩余的 $N-5$ 次转移。

做法

先从空串出发进行至多五轮普通动态规划，每次只保留没有出现禁用子串的状态。若 $N\le5$，直接把第 $N$ 轮所有状态的方案数相加。

否则，把长度恰为五的合法状态放入初始向量。建立矩阵时，对每个五字符状态追加两种字符，并逐一检查所有禁用串是否成为新串的后缀。合法转移对应的矩阵元素加一。将矩阵的 $N-5$ 次幂作用于初始向量，最后求向量元素之和。

每次追加时，旧串已经合法，任何首次出现的禁用子串必然包含新字符并以它结尾，所以后缀检查既不会漏判，也不会误判。状态保留最后五个字符，而最长禁用串长度为六，因此状态包含决定下一次合法性的全部信息。矩阵快速幂只是批量执行相同的合法转移，所得计数与逐字符动态规划一致。

复杂度

设字符集大小为 $2$。状态数固定为 $32$。建立转移的复杂度为 $O(32M)$，矩阵快速幂的时间复杂度为 $O(32^3\log N)$，空间复杂度为 $O(32^2+M)$。