AT_agc040_c Neither AB nor BA
题目大意：
一个由 \(ABC\) 构成的串是好的，当且仅当可以通过不删 \(AB\) 和 \(BA\) 的相邻的两个字符把它删空。
现在给定 \(n\)，求长度为 \(n\) 的字符串有多少是好的。
\(n \le 10^7,2 | n\)。
解题思路：
首先注意到 \(C\) 这个字符是没有施加任何限制的，所以可以看成任意填 \(A/B\)。
那么现在变成了如何判定一个 \(AB\) 串是否合法。
因为 \(AA\) 和 $BB 形的 删除可能导致了 \(ABABABABAB\) 这种数量很多但不能删的情况。
也就是这样刻画会非常复杂。
但注意到因为是一次删两个，所以奇偶性永远不会变。
这样我们就找到了永恒的东西。
然后套套路，将偶数位置的 \(A/B\) 切换，那么一次就是删一个 \(AB/BA\) 了。
这样就很好了啊，因为只要 \(A,B\) 同时有，就一定会相交。
相交就意味着一定可以删除。
所以现在的问题就变为了 \(AB\) 不能有绝对众数，\(C\) 这时候就是用来平衡的了。
因为不能有绝对众数，而绝对众数只能有一个，所以简单容斥一下就好了。
\(O(n)\)。