自动搬运

查看原文

来自洛谷，原作者为

	Refun **

搬运于2025-08-24 21:55:58，当前版本为作者最后更新于2018-04-03 10:38:28，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

第一次做在AC自动机上跑DP的题……

之前做的好像都是乱搞

学长说AC自动机的DP都非常套路

大部分f[i][j]表示当前在节点j,且串长为i时的情况，

有时再加一维表示这个状态里面包含了哪些东西

而且AC自动机的DP会经常让你用矩阵乘法优化

那么对于这个题，我们可以先将AC自动机建立出来，然后搞一个简单的容斥

用所有的情况减去不可读的情况。

那么那些是不可读的情况呢？当然就是跑不到单词结尾节点的情况喽……

定义f[i][j]表示当前在j点且串长为i时不经过单词结尾的路径条数

然后从父亲往儿子转移即可

注意如果一个单词的后缀是一个可读单词(即fail指针指向可读单词的结尾节点)

那么这个单词一定也是可读的，我们就不能往这个单词走了

话说之前我好像做过类似的不过没有吸取教训QvQ活该WA好久

代码