题目
分析
感觉思路比较神仙。
对于按位与和按位或两种运算，显然每一位是独立的，可以分开考虑。
对于某一位，「与 \(0\)」会将这一位变成 \(0\)，「或 \(1\)」会将这一位变成 \(1\) ，「与 \(1\)」和「或 \(0\)」不会改变这一位的值。前两种操作会改变这一位的值，而后两种不会。将前两种称为「关键操作」，那么某一位最终的值取决且仅取决于这一位的最后一次「关键操作」是「与 \(0\)」还是「或 \(1\)」。如果是前者或者不存在关键操作，最终的值就是 \(0\) ，否则是 \(1\) 。
接下来就比较魔幻了。对于每一位，把每个操作符的右操作数（即题目中给定的 \(a_i\)）从右到左 排成一个字符串。假定已经填入了操作符，把这些操作符中与视作 \(1\) ，或视作 \(0\) ，也 从右到左 排成一个字符串。那么，最后一个关键操作就是这两个字符串第一个不相等的地方。换句话说，比较这两个字符串，如果操作符的字符串大（即最后一个关键操作是与 \(0\) ），最终结果就是 \(0\) ，否则是 \(1\) 。
有了这个奇妙的结论，把每一位的右操作数字符串处理出来，从小到大排序（下文中位的「前」「后」是按照这个顺序排序的）。如果把操作符字符串放在某两位的右操作数字符串之间，那么前面的所有位都是 \(0\) ，后面的所有位都是 \(1\) 。如果 \(r_i\) 中最靠前的 \(1\) 在最靠前的 \(0\) 之前，则无解；否则可以确定合法的操作符字符串在哪两位之间，答案就是字典序在这两位的字符串之间的串的数量。
代码
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <string>
using namespace std;
namespace zyt
{
const int N = 1e3 + 10, M = 5e3 + 10, P = 1e9 + 7;
int arr[N][M], val[M], id[M];
basic_string<int> s[M];
bool cmps(const int a, const int b)
{
return s[a] < s[b];
}
int work()
{
int n, m, q;
scanf("%d%d%d", &n, &m, &q);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
scanf("%1d", &arr[i][j]);
for (int i = 1; i <= m; i++)
{
id[i] = i;
for (int j = n, tmp = 0, cnt = 0; j > 0; j--)
{
tmp = tmp * 2 + arr[j][i], ++cnt;
if (j == 1 || cnt == 16)
s[i] += tmp, tmp = cnt = 0;
}
}
sort(id + 1, id + m + 1, cmps);
for (int i = 1; i <= m; i++)
for (int j = n; j > 0; j--)
val[i] = (val[i] * 2LL + arr[j][i]) % P;
val[m + 1] = 1;
for (int i = 1; i <= n; i++)
val[m + 1] = val[m + 1] * 2LL % P;
id[m + 1] = m + 1;
while (q--)
{
bool flag = false, no_ans = false;
static int r[M];
for (int i = 1; i <= m; i++)
scanf("%1d", r + i);
for (int i = 1; i <= m; i++)
if (r[id[i]] == 1)
flag = true;
else
no_ans |= flag;
if (no_ans)
puts("0");
else
{
bool flag = false;
for (int i = 1; i <= m; i++)
if (r[id[i]] == 1)
{
flag = true;
printf("%d\n", (val[id[i]] - val[id[i - 1]] + P) % P);
break;
}
if (!flag)
printf("%d\n", (val[id[m + 1]] - val[id[m]] + P) % P);
}
}
return 0;
}
}
int main()
{
return zyt::work();
}