题解

第\(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 
    
     #define fi first#define se second#define pii pair
     
      #define space putchar(' ')#define enter putchar('\n')#define mp make_pair#define MAXN 100005#define pb push_back//#define ivorysiusing namespace std;typedef long long int64;typedef unsigned int u32;template
      
       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
       
        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();}