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

· · 题解

翻译一下附件里的题解。

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

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

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

我们有两种算法。

算法 1:从顶到底的搜索

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

搜索前一半的问号，直到剩下最低 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)。

算法 2:从底到顶的搜索

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

首先我们假设 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)，可以通过。