A – 杀毒软件
这套题里面质量最好的题（虽然跟 BZOJ 的某题比较像）。
我们先考虑把所有的病毒串加到 AC 自动机里去，然后再考虑一个 DP 转移，设 \( dp[i][j] \) 为当前第 \(i\) 个字符匹配于自动机节点 \(j\) 上的方案数。发现数据范围很小，所以其实这个可以矩阵优化。建完 AC 自动机之后，我们针对 \(a_i = 0, 1, -1\) 算三个矩阵。算完这个之后用线段树来维护就可以了。（复杂度上天了）
实测矩阵乘法的时候剪枝可以快 10s 的样子。
这套题里面质量最好的题（虽然跟 BZOJ 的某题比较像）。
我们先考虑把所有的病毒串加到 AC 自动机里去，然后再考虑一个 DP 转移，设 \( dp[i][j] \) 为当前第 \(i\) 个字符匹配于自动机节点 \(j\) 上的方案数。发现数据范围很小，所以其实这个可以矩阵优化。建完 AC 自动机之后，我们针对 \(a_i = 0, 1, -1\) 算三个矩阵。算完这个之后用线段树来维护就可以了。（复杂度上天了）
实测矩阵乘法的时候剪枝可以快 10s 的样子。