题解：CF1698G Long Binary String

Petit_Souris · 2025-06-26 09:55:14 · 题解

very cool problem

将问题表示成 \bmod 2 意义下形式幂级数的形式。

首先把前导零删掉，最后答案平移一下。设 F(x) 为输入串对应的多项式，那么我们要求的就是选择一些 F(x)x^t 加起来，得到形如 1 + x ^ k 的结果，那么答案就是 (0, k)。

显然最后式子可以表示成 F(x)G(x) 的形式，G(x) 为任意多项式。即求 F(x)G(x) = 1 + x ^ k。

两边对 F(x) 取模，得到 x ^ k \equiv 1 \pmod {F(x)}（这是因为在 \bmod 2 意义下）。

看起来很像一个 BSGS 问题，而由于 \deg F(x) < n，因此根据抽屉原理，k\le 2^{n - 1}。（\bmod F(x) 后只有 0\sim n - 2 次项，每个系数两种方法，因此 2^{n - 1} + 1 个 k 中至少有两个相同的）

因此我们设 k = uB - v，其中 B = \mathcal O(2^{n / 2})。那么即求 x ^ {uB} \equiv x ^ v \pmod {F(x)}。预处理出 [0, B] 内的 x ^ v 和 x ^ {uB}，枚举 u 找到对应的 v 即可。