题解
第(i)个数之前的符号是或那么记为0，是与就记为1，得到一个二进数x
然后按位分开考虑，如果这一行是1那么记为1，如果这一位数位0记为0，得到一个二进制数(b_i)
第(N)行是最高位，如果这一位是1的话，需要有(x < b_i)
然后我们把所有(b_i)从大到小排个序，对于一个(r)要满足按照(b)的顺序所有的0不在1的前面，然后找到第一个0出现的(b_i)，最后一个1出现的(b_j)，答案是(b_j - b_i)
代码
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define space putchar(' ')
#define enter putchar('
')
#define mp make_pair
#define MAXN 100005
#define pb push_back
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
template<class T>
void read(T &res) {
res = 0;char c = getchar();T f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {putchar('-');x = -x;}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
const int MOD = 1000000007;
char a[1005][5005],r[5005];
int N,M,Q,id[5005],c[5005],large[5005],tot,val[5005];
int inc(int a,int b) {
return a + b >= MOD ? a + b - MOD : a + b;
}
int mul(int a,int b) {
return 1LL * a * b % MOD;
}
int fpow(int x,int c) {
int res = 1,t = x;
while(c) {
if(c & 1) res = mul(res,t);
t = mul(t,t);
c >>= 1;
}
return res;
}
int check(int s,int t) {
for(int i = N ; i >= 1 ; --i) {
if(a[i][s] != a[i][t]) {
return a[i][s] > a[i][t];
}
}
return -1;
}
bool cmp(int s,int t) {
int x = check(s,t);
return x == -1 ? s < t : x;
}
void Init() {
read(N);read(M);read(Q);
for(int i = 1 ; i <= N ; ++i) {
scanf("%s",a[i] + 1);
}
for(int i = 1 ; i <= M ; ++i) id[i] = i;
sort(id + 1,id + M + 1,cmp);
for(int i = 1 ; i <= M ; ++i) {
for(int j = N ; j >= 1 ; --j) {
c[i] = inc(inc(c[i],c[i]),a[j][i] - '0');
}
}
large[id[1]] = ++tot;val[tot] = c[id[1]];
for(int i = 2 ; i <= M ; ++i) {
if(check(id[i],id[i - 1]) == -1) large[id[i]] = large[id[i - 1]];
else {large[id[i]] = ++tot;val[tot] = c[id[i]];}
}
val[0] = fpow(2,N);
}
void Solve() {
for(int i = 1 ; i <= Q ; ++i) {
scanf("%s",r + 1);
int zero = tot + 1,one = 0;
for(int j = 1 ; j <= M ; ++j) {
if(r[j] - '0') one = max(one,large[j]);
else zero = min(zero,large[j]);
}
if(zero < one) {puts("0");}
else {out(inc(val[one],MOD - val[zero]));enter;}
}
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Init();
Solve();
}