题解：P3109 [USACO14OPEN] Code Breaking G

_2022gdgzby01 · 2024-11-06 13:32:16 · 题解

考虑容斥，枚举哪些串必然出现，那么贡献为 (-1)^{选中的串数}。

设 f_{i,j} 表示 i 的子树内，i 点往上是 j 这个串的贡献之和，那么总状态数为 O(n+m) ，用 map 存储 f。

将子树的 DP 值与父亲合并时，按串长分类讨论：

若子树串比较长，那么暴力枚举它的前缀状态转移即可。

若父亲串比较长，那么一个子树状态对父亲状态的贡献编码后对应一个区间。

扫描线处理区间，对于相邻的区间内的所有 DP 值整体乘上一个数，线段树维护。

最后沿着线段树上有效节点走，即可不重不漏地得到所有新的状态。

时间复杂度 O(n\log n)。