# 洛谷4424 [hnoi_ahoi2018]寻宝游戏

## 位运算总是很妙妙啊qwq

Posted by yjjr's blog on October 15, 2018 4 minutes to read

# 题目

## 输入输出样例

### 输入样例#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


# 分析

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;
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;
}
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()
{
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;
}