分类讨论

CodeForces CF356E – Xenia and String Problem

这是一种不需要任何数据结构和处理字符串的工具，但细节繁多的做法。

设全串为 $s_{1\dots n}$。不难发现，Gray string 的串长必然是 $2^w-1\quad (w\geq 1)$ 的形式。若其长为 $2^w-1$，我们称其为 $w-1$ 阶 Gray string。

同时用归纳法可以证明，设一个 $w$ 阶 Gray string 的起始位置为 $x+1$（其终到位置为 $x+2^{w+1}$），那么必然有 $$\forall k\in\{0,1,\cdots,w\},s_{x+2^k}=s_{x+2^k+2^{k+1}}=s_{x+2^k+2\times 2^{k+1}}=\cdots=s_{x+2^k+(2^{w-k}-1)2^{k+1}}\\ \forall i,j,0\leq i<j\leq w,s_{x+2^i}\neq s_{x+2^j}$$ 成立。例如一个 $3$ 阶 Gray string 可以被描述为 $\mathtt{abacabadabacaba}$。 （更多…）