奇怪的 XX 怎么冒出来的？（0）

· · 题解

在这个系列 blog 中我会尽量解释一些 Ad-hoc 问题的解法是如何在一定观点下，自然呈现的。本次的题目是：CF1421E。

首先考虑一个变换中的不变量。那么我们有：

v(\texttt{+}) = v(\texttt{-})^2, v(\texttt{-}) = v(\texttt{+})^2 \implies v(\texttt{+}).

然后因为我们希望就是你在一个字符串前面添加一个 \texttt{+} 或 \texttt{-} 不要损失信息，所以我们最好有消去律，另外，空串对应了单位元。这么说，这个东西应该是一个群。那么：

\langle x, y \mid x^2=y,y^2=x \rangle = \mathbb Z / 3 \mathbb Z.

那么 x, y 分别对应 1, 2 或 2, 1 就是自然的了。

说明 2 \mathrm{cnt}(\texttt{+}) + \mathrm{cnt}(\texttt{-}) \in 1 + 3 \mathbb Z 之后，剩下的过程就可以去看其他题解了。