标签：智商题，位运算，数论
题目
题目描述
某大学每年都会有一次Mystery Hunt的活动，玩家需要根据设置的线索解谜，找到宝藏的位置，前一年获胜的队伍可以获得这一年出题的机会。
作为新生的你，对这个活动非常感兴趣。你每天都要从西向东经过教学楼一条很长的走廊，这条走廊是如此的长，以至于它被人戏称为infinite corridor。一次，你经过这条走廊时注意到在走廊的墙壁上隐藏着\(n\)个等长的二进制的数字，长度均为\(m\)。你从西向东将这些数字记录了下来，形成一个含有\(n\)个数的二进制数组\(a_1,a_2,...,a_n\)。
很快，在最新的一期的Voo Doo杂志上，你发现了\(q\)个长度也为\(m\)的二进制数\(r_1,r_2,...,r_q\)。
聪明的你很快发现了这些数字的含义。
保持数组\(a_1,a_2,...,a_n\)的元素顺序不变，你可以在它们之间插入\(∧\)（按位与运算）或者\(∨\)（按位或运算）。例如：\(11011∧00111=00011\)，\(11011∨00111=11111\)。
你需要插入\(n\)个运算符，相邻两个数之前恰好一个，在第一个数的左边还有一个。如果我们在第一个运算符的左边补入一个0，这就形成了一个运算式，我们可以计算它的值。与往常一样，运算顺序是从左到右。有趣的是，出题人已经告诉你这个值的可能的集合——Voo Doo杂志里的那些二进制数\(r_1,r_2,...,r_q\)，而解谜的方法，就是对\(r_1,r_2,...,r_q\)中的每一个值\(r_i\)，分别计算出有多少种方法填入这\(n\)个计算符，使的这个运算式的值是\(r_i\)。
然而，infinite corridor真的很长，这意味着数据范围可能非常大。因此，答案也可能非常大，但是你发现由于谜题的特殊性，你只需要求答案模1000000007的值。
输入输出格式
输入格式
第一行三个数\(n\),\(m\),\(q\)，含义如题所述。
接下来\(n\)行，其中第\(i\)行有一个长度为\(m\)的二进制数，左边是最高位，表示\(a_i\)。
接下来\(q\)行，其中第\(i\)行有一个长度为\(m\)的二进制数，左边是最高位，表示\(r_i\)。
输出格式
输出\(q\)行，每行一个数，其中的\(i\)行表示对于\(r_i\)的答案。
输入输出样例
输入样例#1
5 5 1
01110
11011
10000
01010
00100
00100
输出样例#1
6
输入样例#2
10 10 3
0100011011
0110100101
1100010100
0111000110
1100011110
0001110100
0001101110
0110100001
1110001010
0010011101
0110011111
1101001010
0010001001
输出样例#2
69
0
5
说明
对于 10% 的数据，\(n \le 20, m \le 30, q = 1\)
对于另外 20 的数据，\(n \le 1000, m \le 16\)
对于另外 40 的数据，\(n \le 500, m \le 1000\)
对于全部的数据\(1≤n≤1000,1≤m≤5000,1≤q≤1000\)。
分析
本题膜了一波题解，思路真的好妙啊qwq
考虑将操作序列转化为01序列
可以将\(∨\)视为0,\(∧\)视为1
结论：如果i前面的运算符和第j位相同那么运算结果就不会改变
转化之后发现就是要求操作序列（用二进制表示）<x
转化为二进制序列比大小
ans=最小的结果为1的01串-最大的结果为0的01串
code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read(){
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
//**********head by yjjr**********
const int maxn=5e3+6,mod=1e9+7;
int n,m,q,c[2],up,dw,a[maxn],b[maxn],s[maxn],t[maxn],qp[maxn];
char st[maxn];
int main()
{
n=read(),m=read(),q=read();
qp[1]=1;rep(i,2,n+1)qp[i]=(qp[i-1]<<1)%mod;
rep(i,1,m)a[i]=i;
rep(i,1,n){
scanf("%s",st+1);
c[0]=0,c[1]=m;
rep(j,1,m)st[j]=='1'?s[j]=(s[j]+qp[i])%mod:++c[0];
dep(j,m,1)b[c[st[a[j]]-48]--]=a[j];
swap(a,b);
}
rep(i,1,m)t[i]=s[a[i]];t[m+1]=qp[n+1];
while(q--){
scanf("%s",st+1);
up=m+1,dw=0;
dep(i,m,1)if(st[a[i]]=='0'){dw=i;break;}
rep(i,1,m)if(st[a[i]]=='1'){up=i;break;}
printf("%d\n",up<dw?0:(t[up]-t[dw]+mod)%mod);
}
return 0;
}
