主要思路
这也太他妈毒瘤了吧。
这个题首先肯定是要离线的，在线肯定没发做。事实上，我们可以对这个匹配分为三类：在上升链上、过 LCA 或者是在下降链上。这三者可以分开进行统计。上升链和下降链可以通过对询问字符串正反建 AC 自动机、然后在原树上做 DFS 即可；经过 LCA 的链有点难处理，发现能参与匹配的字符个数是与 \(|\text{询问串}|\) 相关的，所以我们把左右链的两个部分拼起来，然后单独跑 KMP 即可。
代码好长，狗屎一般。
Continue reading →这也太他妈毒瘤了吧。
这个题首先肯定是要离线的，在线肯定没发做。事实上，我们可以对这个匹配分为三类：在上升链上、过 LCA 或者是在下降链上。这三者可以分开进行统计。上升链和下降链可以通过对询问字符串正反建 AC 自动机、然后在原树上做 DFS 即可；经过 LCA 的链有点难处理，发现能参与匹配的字符个数是与 \(|\text{询问串}|\) 相关的，所以我们把左右链的两个部分拼起来，然后单独跑 KMP 即可。
代码好长，狗屎一般。
Continue reading →这套题里面质量最好的题（虽然跟 BZOJ 的某题比较像）。
我们先考虑把所有的病毒串加到 AC 自动机里去，然后再考虑一个 DP 转移，设 \( dp[i][j] \) 为当前第 \(i\) 个字符匹配于自动机节点 \(j\) 上的方案数。发现数据范围很小，所以其实这个可以矩阵优化。建完 AC 自动机之后，我们针对 \(a_i = 0, 1, -1\) 算三个矩阵。算完这个之后用线段树来维护就可以了。（复杂度上天了）
实测矩阵乘法的时候剪枝可以快 10s 的样子。
这题还是蛮有意思，有一些奇怪的细节。
首先，只考虑正串，我们就直接塞进 AC 自动机里做套路 DP 即可。考虑串在后半段的情况，发现其实你只要刻画好前半段后半段即可被自动刻画，所以我们做串的反串并把字符取反塞到正串的 AC 自动机里就可以让字符串出现在后半段。