交互

CF2210E

CF2210E. Binary Strings are Simple?

• 交互。
• 猜测长度为 $N$ 的 01 串。
• 每次询问子串 $S[l\dots r]$，返回子串所有循环移位的逆序对数 mod 子串长度的集合大小。
• 询问的代价为 $\dfrac{N}{r-l+1}$，总询问代价不超过 $\max(30,3 N)$。
• 最多可以猜测 $2$ 次。

当循环左移 1 时贡献是 $-c_0=c_1-n$，否则是 $c_1$，逆序对在模意义下的增量总是 $c_1$。因此询问实际是 $\#\{x : x=kc_1\bmod N, k\in[1,N]\} = \displaystyle\frac{N}{\gcd(N,c_1)}$。

奇偶。在仅知道 $\gcd(N,c_{1})$ 与 $N$ 的前提下，若 $N$ 为偶数，则 $\gcd(N,c_{1})$ 的奇偶性与 $c_{1}$ 一致。

询问 $[l,i-1]$ 和 $[l,i+1]$（$l$ 是最小的让区间长度为偶数的值，有 $l\in\{1,2\}$），可以归纳由 $i$ 确定出 $i+1$。

允许猜 2 次，必然可以反推出做法是建立各个字符之间相同 / 不相同的关系，然后仅剩一个自由元再猜；接下来可以很自然地想到我们确定每两个相邻字符是相同或不同，并把第一个字符作为自由元。

左半段用前缀，右半段用后缀，代价是调和级数，