AHOI/HNOI2018 寻宝游戏（乱搞）

发表于 |
字数统计: 1,200字 | 阅读时长 ≈ 5min

「AHOI / HNOI2018」寻宝游戏

问题描述

某大学每年都会有一次 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$ 的元素顺序不变,你可以在它们之间插入 $\wedge$（按位与运算）或者 $\vee$（按位或运算）两种二进制运算符。例如：$11011 \wedge 00111=00011,11011 \vee 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$ （$10^9 + 7$，一个质数）的值。

输入格式

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

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

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

输出格式

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

样例输入

5 5 1
01110
11011
10000
01010
00100
00100

样例输出

6

提示

对于 $10\%$ 的数据，$n \le 20, m \le 30$，$q = 1$

对于另外 $20\%$ 的数据，$n \le 1000$，$m \le 16$

对于另外 $40\%$ 的数据，$n \le 500$，$m \le 1000$

对于 $100\%$ 的数据，$1 \le n \le 1000$，$1 \le m \le 5000$，$1 \le q \le 1000$

这题考验人类智慧。

按位考虑操作后的结果，把每一列压成一个二进制数$b_i$，最下面是最高位。

然后把操作序列也压成一个二进制数$x$，$\&$为1，$|$为0，同样最后的操作是最高位。这样做了之后，发现第$i$为1当且仅当$x<b_i$

那么就可以确定$x$的取值范围了，为了方便，将$b_i$排序，然后分别找到$x$的上界和下界，答案就是$b_{up}-b_{low}$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int mod=1e9+7;
int add(int a,int b){a+=b;return a>=mod?a-mod:a;}
int sub(int a,int b){a-=b;return a<0?a+mod:a;}
int mul(int a,int b){return 1ll*a*b%mod;}
int n,m,q,Rank[5005],val[5005],pow2[1005];
struct node{int id;char s[1005];}B[5005];
bool operator<(node a,node b)
{
	for(int i=n;i>=1;i--)
	if(a.s[i]!=b.s[i])return a.s[i]<b.s[i];
	return 0;
}
char s[1005][5005],s0[5005];
int Get(char t[])
{
	int ans=0;
	for(int i=1;i<=n;i++)if(t[i]=='1')ans=add(ans,pow2[i-1]);
	return ans;
}
int main()
{
	int i,j,k,Max,Min;
	scanf("%d%d%d",&n,&m,&q);
	pow2[0]=1;
	for(i=1;i<=n;i++)pow2[i]=mul(2,pow2[i-1]);
	for(i=1;i<=n;i++)scanf("%s",&s[i][1]);
	for(i=1;i<=n;i++)
	for(j=1;j<=m;j++)B[j].s[i]=s[i][j];
	for(i=1;i<=m;i++)B[i].id=i;
	sort(B+1,B+m+1);
	for(i=1;i<=m;i++)val[i]=Get(B[i].s);
	val[m+1]=pow2[n];
	for(i=1;i<=m;i++)Rank[B[i].id]=i;
	for(i=1;i<=q;i++)
	{
		scanf("%s",&s0[1]);
		Max=0;Min=m+1;
		for(j=1;j<=m;j++)
		{
			if(s0[j]=='1')Min=min(Min,Rank[j]);
			else Max=max(Max,Rank[j]);
		}
		if(Max>=Min)puts("0");
		else printf("%d\n",sub(val[Min],val[Max]));
	}
}