题解：AT_arc110_e [ARC110E] Shorten ABC

· · 题解

将 ABC 看作 1,2,3，每次选择相邻两个不同的并将他们改为两者的异或。

特判初始时所有数相等，此时答案为 1，现在考虑怎么判定 s 能否变为 t。

我们声称 s 从前往后每次找最短的区间使得异或和等于 t 这一位的值匹配即可。合法当且仅当匹配过程中没有匹配出边界最后剩下的后缀异或和为 0。证明考虑先说明任意一个序列都可以操作为长度为 1 的序列，权值为异或和，除了初始长度为奇数大于 1 的且所有数相同的序列，这是容易归纳的。那么进一步可以知道匹配的每一段都不可能是长度为奇数大于 1 全相同否则应该匹配更短的，而后缀由于异或和为 0 一定可以放到最后一个 t_m 里一起，所以容易证明这是充分条件，另一方面必要条件也容易说明。

从前往后 DP，f_i 表示有多少个 t 能恰好匹配到 i 即可，复杂度线性。