【题解】[HNOI/AHOI2018]寻宝游戏

[HNOI/AHOI2018]寻宝游戏

给定 $n$ 个长度为 $m$ 的 $01$ 串，最前面补一个 $0$，现在需在每个串之前插入 $\text{and}$ 或 $\text{or}$ 两种运算符。
$q$ 组询问，每次给一个长 $m$ 的 $01$ 串，每次询问有多少种插入 $n$ 个运算符的方法使运算结果为给定字符串。
$1\le n,q\le 1000,1\le m\le 5000$。

$\text{Solution:}$

由于是二进制位运算，所以分位考虑。

将原来 $n$ 个二进制数，竖着排列，然后竖过来看。对于所有 $n$ 个字符串的第 $i$ 位，按照原字符串编号 $n-1$ ，从高位到低位排列下来，会得到一个长度为 $n$ 的 $01$ 串，比如：

1: 00[1]01
2: 01[0]11
3: 10[0]11
4: 00[0]10

0001

若我希望这一位答案是 $x(x\in\{0,1\})$，那么有等式：

$$0\oplus 1\oplus 0\oplus 0\oplus 0=x$$

其中 $\oplus$ 都是运算符。

我们发现，$k\ \text{and}\ 0=0$，$k\ \text{or}\ 1=1$ 这两种方案后结果是固定的。

玄幻的一步来了 考虑将运算的 $n$ 个元素也变为一个二进制数。其中 $\text{and}$ 为 $1$，$\text{or}$ 为 $0$。按照运算顺序从后往前，从高位到低位写作一个二进制数字。

例如：

$$0\ \text{or}\ 1\ \text{or}\ 0\ \text{or}\ 0\ \text{or}\ 0=1$$

其中运算符产生的二进制数为 $0000$。

$$0\ \text{and}\ 1\ \text{or}\ 0\ \text{or}\ 0\ \text{or}\ 0=0$$

运算符产生的二进制数为 $0001$。

可以证明，若令 $n$ 个二进制数第 $i$ 位所产生的二进制数为 $p$，运算符产生的二进制数为 $q$。那么若当前这一位答案为 $1$，当且仅当 $p > q$，其中 $>$ 就是数字的大小比较。

例如上述 $p=0001$，而第一个等式中 $q=0000$，$p>q$，答案为 $1$。第二个等式中 $q=0001$，$p\le q$，答案为 $0$。

粗略证明如下：

我们令 $p[i]$ 表示 $p$ 这个二进制数的从高到低第 $i$ 位，$q$ 同理。我们观察到，对于一个相同的 $i$，$p[i]$ 是在运算符 $q[i]$ 右侧的数字。

若希望得到 $1$，我们总认为 $\text{or}$ 比 $\text{and}$ 要更为合适，因为他让数字变为 $1$ 的要求更低。

若 $p<q$，那么一定存在一个高位 $i$ 使得 $p[i]=0,q[i]=1$。即在原序列中对应着，这个 $q[i]$ 对应的 $\text{and}$，其右侧是 $0$，那么如果这样，$1$ 就不可能继续向着更后面的位置传播。也就是说，每个 $p[i]=0,q[i]=1$ 的位置都会阻碍当前的 $1$ 向后继续传播，因此可以证明若 $p<q$，则答案一定为 $0$。

若 $p=q$，答案也为 $0$，可以这样证明：考虑一个 $\text{and}$，由于 $p=q$，因此其右侧一定为 $1$，接着考察左侧。假设左侧是 $1$，那么答案为 $1$，继续向右传递；而若左侧是 $0$，那么答案为 $0$，向右传递。但是由于第一个位置是 $0$，所以任何 $\text{and}$ 的左侧必然不会存在 $1$。再考虑 $\text{or}$，由于 $\text{or}$ 对应 $0$，因此其右侧必然为 $0$，则取值取决于左侧。相当于在进行传递，而完全不改变值。

若 $p>q$，答案为 $1$ 证明如下：考虑一个位置使得 $p[i]=1,q[i]=0$，那么由于当前运算是 $\text{or}$，且其右侧为 $1$，那么答案必然为 $1$。因此只需要考察最高的满足 $p[i]=1,q[i]=0$ 的位置即可证明当前答案为 $1$。

那么就有：用上述方法将 $n$ 个长 $m$ 的二进制数转变为 $m$ 个长度为 $n$ 的二进制数，那么对于一个询问的二进制数字，其每一位相当于对运算符的二进制数的一个限制。

即对于询问串为 $0$ 的位，运算符串大小应 $\le$ 该位的串。为 $1$ 则运算符串大小 $>$ 该位的串。

因此可以先对 $m$ 个串基数排序，对于每一个询问，找到所有询问串中值为 $0$ 的位置，求出这些二进制数的最小值 $\text{mn}$，同样找到值为 $1$ 位置的二进制数的最大值 $\text{mx}$。若 $\text{mx}>\text{mn}$，则无解，否则答案为 $\text{mn}-\text{mx}$。

时间复杂度 $\mathcal{O}(nm+q(n+m))$。