洛谷P4424 [HNOI/AHOI2018] 寻宝游戏题解

题目链接：P4424 [HNOI/AHOI2018] 寻宝游戏

题意：

某大学每年都会有一次 Mystery Hunt 的活动，玩家需要根据设置的线索解谜，找到宝藏的位置，前一年获胜的队伍可以获得这一年出题的机会。

作为新生的你，对这个活动非常感兴趣。你每天都要从西向东经过教学楼一条很长的走廊，这条走廊是如此的长，以至于它被人戏称为 infinite corridor。一次，你经过这条走廊时注意到在走廊的墙壁上隐藏着 $n$ 个等长的二进制的数字，长度均为 $m$。你从西向东将这些数字记录了下来，形成一个含有 $n$ 个数的二进制数组 $a_1,a_2,…,a_n$。

很快，在最新的一期的 Voo Doo 杂志上，你发现了 $q$ 个长度也为 $m$ 的二进制数 $r_1,r_2,…,r_q$。

聪明的你很快发现了这些数字的含义。

保持数组 $a_1,a_2,…,a_n$ 的元素顺序不变，你可以在它们之间插入 $\land$（按位与运算）或者 $\lor$（按位或运算）。例如：$11011\land 00111=00011$，$11011\lor 00111=11111$。

你需要插入 $n$ 个运算符，相邻两个数之前恰好一个，在第一个数的左边还有一个。如果我们在第一个运算符的左边补入一个 0，这就形成了一个运算式，我们可以计算它的值。与往常一样，运算顺序是从左到右。有趣的是，出题人已经告诉你这个值的可能的集合—— Voo Doo 杂志里的那些二进制数 $r_1,r_2,…,r_q$，而解谜的方法，就是对 $r_1,r_2,…,r_q$ 中的每一个值 $r_i$，分别计算出有多少种方法填入这 $n$ 个计算符，使的这个运算式的值是 $r_i$。

然而，infinite corridor 真的很长，这意味着数据范围可能非常大。因此，答案也可能非常大，但是你发现由于谜题的特殊性，你只需要求答案模 $1000000007$ 的值。

输入格式：

第一行三个数 $n,m,q$，含义如题所述。

接下来 $n$ 行，其中第 $i$ 行有一个长度为 $m$ 的二进制数，左边是最高位，表示 $a_i$。

接下来 $q$ 行，其中第 $i$ 行有一个长度为 $m$ 的二进制数，左边是最高位，表示 $r_i$。

输出格式：

输出 $q$ 行，每行一个数，其中的 $i$ 行表示对于 $r_i$ 的答案。

数据范围：

$1\leq n\leq 1000,1\leq m\leq 5000,1\leq q\leq 1000$。

依次考虑每一个数字 $i$ 的每一位 $j$ 。方便起见，我们定义最右侧的那一位是最高位。

注意到 $x\land 0=0$ 和 $x\lor 1=1$ 这两个操作，无论前面是什么结果，到这里就肯定是 $0$ 和 $1$ 。

注意到 $x \lor 0=x$ 和 $x \land 1=x$ 这两个操作，无论前面是什么结果，到这里都不会变。

要使得第 $j$ 位的运算结果是 $1$ ，因此最后一个 $x\lor 1$ 的位置要在 $x\land 0$ 的前面。

考虑记操作序列为 $\rm op$ ，其中 $\mathrm{op}(i):= [\textbf{option}=\, \land]$ 。也就是把 $\lor$ 记为 $0$ ，$\land$ 记为 $1$ 。

然后把第 $j$ 位的数提出来作为一个长度为 $n$ 的二进制数，记为序列 $x_j$ 。

那么根据刚才我们定义的序列，这个问题就转化为了 $x_j > \mathrm{op}$ 。例如

$\begin{aligned} & x_j=1011, \mathrm{op}=0011, x_j>\mathrm{op} \\[6pt]& 0 \vee 1 \vee 0 \wedge 1 \wedge 1=1 \\[6pt]& x_j=1011, \mathrm{op}=1011, x_j \leq \mathrm{op} \\[6pt]& 0 \wedge 1 \vee 0 \wedge 1 \wedge 1=0 \end{aligned}$

于是我们就把问题转化为了比大小。我们把 $x_j$ 按二进制数的值排序

然后每次判断 $x_j$ 和 $\rm op$ 的大小关系，如果有解可以得到 $x_l \le \mathrm{op} < x_r$ ，答案就是 $x_r - x_l$ 。

时间复杂度 $\mathcal{O}((n+q)m)$ ，排序可以用计数排序。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 1e9 + 7;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
void add(int &x, int y) { (x += y) >= mod ? x -= mod : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(5e3 + 15))

char s[N];
int pw2[N], a[N], b[N], t[N], cnt[2], v[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, m, q; cin >> n >> m >> q; pw2[1] = 1;
    rep(i, 2, n + 1) pw2[i] = pw2[i - 1] * 2 % mod;
    rep(i, 1, m) a[i] = i;
    rep(i, 1, n)
    {
        cin >> (s + 1); cnt[0] = 0; cnt[1] = m;
        rep(j, 1, m) { if(s[j] == '1') add(v[j], pw2[i]); else ++cnt[0]; }
        Rep(j, m, 1) { b[cnt[s[a[j]] - '0']--] = a[j]; } swap(a, b);
    }
    rep(i, 1, m) t[i] = v[a[i]] % mod;
    int mx, mn; t[m + 1] = pw2[n + 1];
    rep(l, 1, q)
    {
        cin >> (s + 1); mx = m + 1, mn = 0;
        Rep(i, m, 1) if(s[a[i]] == '0') { mn = i; break; }
        rep(i, 1, m) if(s[a[i]] == '1') { mx = i; break; }
        if(mx < mn) cout << "0\n";
        else { cout << (t[mx] + mod - t[mn]) % mod << '\n';}
    }
    return 0;
}