Description
给出 (n) 个 (m) 位的二进制数,在每一个二进制数间插入一个 &
或 |
,第 (0) 个数为 (0) , (0,1) 间也要插入符号,共插入 (n) 个符号。
给出 (q) 组询问,每组询问也给出一个二进制数,询问有多少种方式使得从左至右运算后结果为该数。
(1leq nleq 1000,1leq mleq 5000,1leq qleq 1000)
Solution
人类智慧题。
我们可以把每一位单独拿出来处理,将每一位压成一个 (n) 位的二进制数,第 (i) 位为 (a_i) 。越靠右位数越高。
我们对于生成的符号序列,将 &
记为 (1) , 将 |
记为 (0) 。同样越靠右位数越高。记为 (x) 。
考验人类智慧的就是,有这样一个结论:若第 (i) 位运算结果为 (1) ,当且仅当 (x<a_i) 。这个可以感性理解一下,比较直观。
那么我们考虑将 (a_i) 从大到小排序,我们只需找到这样的唯一一个断点,满足断点以左的 (a_i) 对应的那一位均为 (1) ,断点以右的均为 (0) 。
假设断点右边一位为 (loc) ,那么答案就是 (a_{loc-1}-a_{loc}) 。如果没有断点,显然无解。
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1000+5, M = 5000+5, yzh = 1000000007;
int n, m, q, mp[M], cg[M];
char ch[M];
struct tt {
int b[N], id;
bool operator < (const tt &c) const {
for (int i = n; i >= 1; i--)
if (b[i] != c.b[i]) return b[i] > c.b[i];
}
}a[M];
int get_ans(int o) {
int x = 0, y = 0;
for (int i = n; i >= 1; i--) x = (2ll*x%yzh+a[o-1].b[i])%yzh;
for (int i = n; i >= 1; i--) y = (2ll*y%yzh+a[o].b[i])%yzh;
return ((x-y+(o == 1))%yzh+yzh)%yzh;
}
void work() {
scanf("%d%d%d", &n, &m, &q);
for (int i = 1; i <= n; i++) {
scanf("%s", ch+1);
for (int j = 1; j <= m; j++) a[j].b[i] = ch[j]-'0';
a[0].b[i] = 1;
}
for (int i = 1; i <= m; i++) a[i].id = i;
sort(a+1, a+m+1);
for (int i = 1; i <= m; i++) mp[a[i].id] = i;
while (q--) {
scanf("%s", ch+1);
for (int i = 1; i <= m; i++) cg[mp[i]] = ch[i]-'0';
int flag = 0, t = 0;
for (int i = 1; i <= m; i++) {
if (cg[i] && t) {flag = 1; break; }
if (cg[i] == 0) t = 1;
}
if (flag) puts("0");
else {
int flag = 0;
for (int i = 1; i <= m; i++)
if (cg[i] == 0) {printf("%d
", get_ans(i)); flag = 1; break; }
if (!flag) printf("%d
", get_ans(m+1));
}
}
}
int main() {work(); return 0; }