【做题记录】万径人踪灭
trsins
·
·
题解
-
- 算法：$\text{FFT,manacher}
题目：
在一个只包含 a,b 的字符串中选择一个序列，使得
-
位置和字符都关于某条对称轴对称。
-
不能是连续的一段。
求有多少个满足要求的序列，答案对 1e9+7 取模。
n\le 10^5
题解：
upd：修改了部分内容。
首先枚举对称轴，假设我们以 k 为对称轴。
设 p_k 为满足 i<j,a_i=a_j 并且 i,j 关于 k 对称的 (i,j) 的个数。
那么对于这 p_k 个 (i,j)，a_i 与 a_j 要么同时选（因为对称所以必定满足），要么同时不选，共 2^{p_k} 种方案。扣掉空集，共 2^{p_k}-1 种。
\therefore ans=\sum\limits_{k=0}^{n}2^{p_k}-1
注意一下这里 k 可以为 \dfrac{t}{2}(t\in \mathbb{N})，因为对称轴可以为两个字符中间（比如 1,8 就关于 4.5 对称，也就是 4,5 的中间对称）
这里有个关于位置对称的性质：
我们可以根据这个转移。
现在位置对称了，还要满足字符对称。
记字符 a 为 1，字符 b 为 0。
那么可以发现当两字符相等时仅可能为 1+1=2(aa) 或 0+0=0(bb)。而对于 1+0=1(ab) 的情况则需要排除。
由于 aa 和 bb 的情况的数值中间相差了 ab，难以判断是否对称。
这里有个很好用的东西：平方。
平方可以消去数值的负号。
所以我们可以将 aa,bb,ab 所代表的数值各消去 1 ，那么变为 1,-1,0；此时再将它们都平方，那么对称的即变为 1，不对称的还是 0，很好地满足了我们的要求。
\therefore p_{k}=\sum\limits_{i+j=2k}(a_i+a_j-1)^2
非常显然的卷积，\text{FFT} 一卷即可。
但题目中还说“位置不能连续”，说明要扣掉连续的回文子串的个数。
对于回文的对称的子串显然，用 manacher 一弄就好了。