简述
时隔一年之后再学一个新的筛法是不是没救了啊。
这套题里面质量最好的题（虽然跟 BZOJ 的某题比较像）。
我们先考虑把所有的病毒串加到 AC 自动机里去，然后再考虑一个 DP 转移，设 \( dp[i][j] \) 为当前第 \(i\) 个字符匹配于自动机节点 \(j\) 上的方案数。发现数据范围很小，所以其实这个可以矩阵优化。建完 AC 自动机之后，我们针对 \(a_i = 0, 1, -1\) 算三个矩阵。算完这个之后用线段树来维护就可以了。（复杂度上天了）
实测矩阵乘法的时候剪枝可以快 10s 的样子。
这个题还蛮神仙的。主要的思路就是算三元组 \( (p_1, p_2, p_3) \)，满足 \( G(S(p_1, p_2)) = G(S(p_2, p_3)) = G(S(p_1, p_3)) = x \)。我们先考虑 \(G(S(p_1, p_2)) = x\) 的 \((p_1, p_2)\)。假设我们能把这些路径全部求出来，并把这个仅包含有向边 \( S(p_1, p_2) \) 的有向图的入度、出度算出来。如果能算出这种东西的话，发现直接乘法原理可以算出非法的三元组（合法的三元组是没法搞的，因为你还得算 \( (p_1, p_3) \) 的东西才能搞）。如果规定时间内能搞定这个入度出度之后，我们直接 \(\Theta(n)\) 算掉乘法原理那个。搞入度出度可以直接上点分治。