题解：AT_agc058_d [AGC058D] Yet Another ABC String
analysis
·
·
题解
将字符串看作若干个 abcabc 的有序段组成，我们希望序列中的所有极长有序段的长度小于等于 2。
我们给长度为 n 的有序段配上 p_n 的容斥系数，由于不关心位置，我们设出系数的 OGF P。
显然一个极长的有序段会被钦定的操作划成若干个段，于是有 SEQ(P)=1+x+x^2，解出 P=1-\frac{1}{1+x+x^2}。求系数，分式下面是 \{1,1,1,0,\cdots\}，施差分可以得到 P=1-\frac{1-x}{1-x^3}，得到：
P=1-\sum_{i \geq 0}x^{3i}(1-x)\\p_n=\begin{cases}-1 &&&&& n\equiv 0\\1 &&&&& n \equiv 1\\0 &&&&& n \equiv 2 or n=0\end{cases}
挂上三元 GF，设 u=xyz，有：
G=x+y+z+\sum_{i\geq 1}(xyz)^i(x+y+z-3)=\frac{x+y+z-3u}{1-u}\\\frac{1}{1-G}=\frac{1-u}{1-x-y-z+2u}=(1-u)\sum(x+y+z-2u)^i\\
枚举有多少个 u 即可。