|0 和 &1 没有影响

若填‘|’，记为0，若填‘&’，记为1

先只考虑最后一位

若要求最后=1

那么最后一个|1 要在最后一个 &0 后面

将n个数的最后一位拿出来构成一个01序列

填在所有数最后一位之前的运算符也拿出来构成一个01序列

将第n个数所在位置视为最高位

对于最高位来说

如果数字序列 和 运算符序列 都是0或都是1，没有影响

如果数字序列是0，运算符序列是1，即最后是 &0，显然不能最终等于1，所以这种运算符序列不合法

如果数字序列是1，运算符序列是0，及最后是|1，显然一定是1，这种运算符序列合法

如果数字序列始终等于运算符序列，因为没有影响，所以最终开始开始的那个0，此运算符序列也不合法

所以

如果这一位要求是1，在只考虑这一位的情况下，合法的运算符序列是 运算符的01序列<数字的01序列

同理可以推出

如果这一位要求是0，在只考虑这一位的情况下，合法的运算符序列是 运算符的01序列>=数字的01序列

即可以得到这样的条件：

设合法的运算符序列为S，第i位的数字序列为Ai

若p的第i位为1，则S<Ai  ①

若p的第i位为0，则S>=Ai ②

记①中最小的Ai为 up，②中最大的Ai为down

所以满足所有位的要求的S的个数=up-down

 

计算个数开始想的是高精减，题目要求取模，直接哈希即可

 

#include
     
      #include
      
       #define N 5001using namespace std;const int mod=1e9+7;int bit[N];char s[N];int has[N];int sa[N],now[N];int main(){    int n,m,q;    scanf("%d%d%d",&n,&m,&q);    bit[0]=1;    for(int i=1;i<=n;++i)     {        bit[i]=bit[i-1]<<1;        bit[i]-=bit[i]>=mod ? mod : 0;    }    for(int i=1;i<=m;++i) sa[i]=i;    int c[2];    for(int i=1;i<=n;++i)    {        c[1]=c[0]=0;        scanf("%s",s+1);        for(int j=1;j<=m;++j)        {            has[j]=has[j]+(s[j]-'0')*bit[i-1];            has[j]-=has[j]>=mod ? mod : 0;            c[s[j]-'0']++;        }        c[1]+=c[0];        for(int j=m;j;--j) now[c[s[sa[j]]-'0']--]=sa[j];        swap(sa,now);    }    int up,down;    for(int t=1;t<=q;++t)    {        up=m+1; down=0;        scanf("%s",s+1);        for(int i=1;i<=m && up==m+1;++i)            if(s[sa[i]]-'0') up=i;        for(int i=m;i && !down;--i)            if(!(s[sa[i]]-'0')) down=i;        if(up