题解：P13381 [GCJ 2011 #3] Mystery Square

翻译一下附件里的题解。

直接枚举 $2^{40}$ 种情况不可能，所以考虑分治。

设问号数为 $q$，$t=\lfloor \frac {|S|} 2 \rfloor$，下文中 $n$ 为 $S$ 代表的数。

记最低 $t$ 位为低位，其他为高位。

我们有两种算法。

此算法用于解决高位的问号数较少的情况。

搜索前一半的问号，直到剩下最低 $t$ 位。

设 $L$ 为此时把低位所有 ? 设为 $0$ 的值，$R$ 为此时把低位所有 ? 设为 $1$ 的值。那么可能的 $x$ 范围显然为 $\sqrt{L} \leq x \leq \sqrt{R}$。

然后你会发现，如果 $x$ 与 $x+1$ 同时在范围内，则 $L \leq x^2<(x+1)^2 \leq R$。

但是因为 $x \geq \sqrt{L} \geq 2^t$ 所以 $R-L<=2^t<2x+1=(x+1)^2-x^2$，所以范围内至多只有一个数，配合 $O(\log n)$ 的开根可以做到 $O(2^{\frac q 2}\log n)$。

此算法用于解决低位的问号数较少的情况。

首先我们假设 $x \equiv 1 (\bmod \ 2)$，因为对于 $x \equiv 0 (\bmod \ 2)$ 的情况，直接把最低的 $2$ 位设成 $0$ 然后砍掉递归即可。

然后我们考虑如何用模 $2^{k-1}$ 可能作为答案的 $x$ 推出模 $2^{k}$ 可能作为答案的 $x$。

令 $y \in \{0,1,2,3\}$，$0 \leq x < 2^{k-1}$，我们有 $n \equiv (2^{k-1}y+x)^2 \equiv (2^{2k-2}y^2+2 \times 2^{k-1}yx+x^2) (\bmod \ 2^{k+1})$。

不妨假设 $2k-2 \geq k+1$，即 $k\geq 3$，对于 $k \leq 2$ 直接枚举一下即可。

然后可以得到 $n \equiv 2^kxy+x^2 (\bmod \ 2^{k+1})$

又因为 $x \equiv 1 (\bmod 2)$，所以 $n \equiv 2^ky+x^2 (\bmod 2^{k+1})$，即我们可以确定 $y$ 的奇偶性，那么就可以求出模 $2^k$ 意义下 $x$ 的值。

那么我们只需要让 $k = t+1$，这时因为 $2^{2t} \leq n < 2^{2(t+1)}$，所以直接把模 $2^t$ 意义下的可能作为答案的 $x$ 检查即可，并且由这个可以看出是 $n$ 与 $x$ 是一一对应的。

于是我们只需要搜索 $O(2^{\frac q 2})$ 种情况并且边搜索边算出 $x$ 即可。

然后再考虑一下加上递归的总复杂度，你会发现这个总复杂度会是 $O(2^{\frac q 2}\log n)$ 的。

两个算法拼起来，总复杂度为 $O(\sum 2^{\frac q 2}\log n)$，可以通过。