AC自动机专题:配合矩阵快速幂:POJ-2778

传送门:https://vjudge.net/problem/POJ-2778

题目大意:

给你一个长度为n($n<=2e9$)的字符串S.每个字符可填一个小写字母.再给你m个模式串,代表S中不能含有的子字符串.问你有多少种合法的方案?($\sum m<=100$)

题目思路:

这题的小数据版:BZOJ-1030

其实这题最直接的思路就是:每一位有几种选择,然后直接计数原理乘起来即可.

但问题是:某一位能填写什么被之前填写了什么给限制了.所以我们需要一种方便表示状态的东西:Trie图.

画一张Trie图模拟几遍后发现在填写S的过程,其实是在Trie图上转移(游走)的过程.那么现在我们的需求变成:游走的过程中不允许走到树的叶子节点.(因为走到叶子节点代表了一个完整的匹配,导致不合法).

那么问题就转换为:求从根节点走n步,中途不到达叶子节点所产生的不同的路径数.(一个路径代表一种填写方案).

离散数学里学过,邻接矩阵做m次乘法代表着从x到y的长度为m的不同通路数.(见离散数学P310).所以我们可以对Trie图建邻接矩阵,然后跑矩阵快速幂.

这里需要注意的是:如何防止中途不到达叶子节点?

做法:对叶子节点标记flag.将有flag的节点称之为危险节点．在ＢＦＳ的时候，若某个点的fail指针指向了一个危险节点，那么该点应该也是危险节点.（这里注意理解ｆａｉｌ指针的含义．fail指针本质上是一个字符串前缀的后缀集合.）这里有个思维死角是:在字符串Ａ上转移时可能会匹配出字符串Ｂ.所以在BFS的时候flag标记需要转移扩散．

之后在建图的时候当某个节点指向的点是危险节点则不建边.这样保证了不管在哪个字符串上，都不可能达到叶子节点的状态.

注意点２：这题卡long long 的复杂度．在做矩阵乘法的时候，先将乘法部分提出去算，转成int.再做加法(这时的加法是int加法了)．可以快很多

AC代码:https://paste.ubuntu.com/p/ZpySNR4qBM/

时间复杂度:$O(m^{3}logn)$