Loj 2494 寻宝游戏

Posted on | Views:

巧妙的构造.

若第 $i$ 个数之前的运算符号是 or ,就将这个位置记作 0, 否则记作 1.

依次连接可以得到一个二进制数 $x$ ,规定第 $n$ 个运算符号对应的数为最高位.

对于第 $i$ 列的所有数,也可以顺次连接得到一个二进制数 $b_i$ ,规定第 $n$ 行的那个数为最高位.

于是可以发现运算结果第 $i$ 位为 1, 当且仅当 $b_i<x$ .

先将所有 $b_i$ 排个序,得到它们的大小关系.

对于每个询问,找出 1 的那些位上最小的 $b_i$ ,找出 0 那些位上最大的 $b_i$ ,即可算出方案数.

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
void print(int x)
{
	if (x >= 10)
		print(x / 10);
	putchar('0' + x % 10);
}
void write(int x, char c)
{
	if (x < 0)
		putchar('-'), x = -x;
	print(x);
	putchar(c);
}
const int P = 1e9 + 7;
int add(int a, int b)
{
	return a + b >= P ? a + b - P : a + b;
}
void inc(int &a, int b)
{
	a = add(a, b);
}
const int N = 1e3 + 10, M = 5e3 + 10;
int n, m, q, a[N][M], rnk[M];
struct info
{
	int id, val;
	int b[N];
	bool operator < (const info &rhs) const
	{
		for (int i = 1; i <= n; ++i)
			if (b[i] != rhs.b[i])
				return b[i] < rhs.b[i];
		return false;
	}
} p[M];
char buf[M];
int main()
{
	n = read(), m = read(), q = read();
	int mx = 1;
	for (int i = 1; i <= n; ++i)
	{
		inc(mx, mx);
		scanf("%s", buf + 1);
		for (int j = 1; j <= m; ++j)
			a[i][j] = buf[j] - '0';
	}
	for (int j = 1; j <= m; ++j)
	{
		p[j].id = j, p[j].val = 0;
		for (int i = n; i >= 1; --i)
		{
			p[j].b[n + 1 - i] = a[i][j];
			inc(p[j].val, p[j].val);
			inc(p[j].val, a[i][j]);
		}
	}
	sort(p + 1, p + 1 + m);
	for (int i = 1; i <= m; ++i)
		rnk[p[i].id] = i;
	while (q--)
	{
		scanf("%s", buf + 1);
		int L = 0, R = mx, pos0 = 0, pos1 = m + 1;
		for (int i = 1; i <= m; ++i)
			if (buf[i] == '0')
				pos0 = max(pos0, rnk[i]);
			else
				pos1 = min(pos1, rnk[i]);
		if (pos0 > pos1)
			write(0, '\n');
		else
		{
			if (pos0 != 0)
				L = p[pos0].val;
			if (pos1 != m + 1)
				R = p[pos1].val;
			write(add(R, P - L), '\n');
		}			
	}
	return 0;
}