洛谷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;
}