[loj2494]寻宝游戏

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 5005
 4 #define mod 1000000007
 5 struct ji{
 6     int a[1005];
 7 }ans,a[N];
 8 int n,m,q,id[N],rk[N];
 9 char s[N];
10 bool cmp(int x,int y){
11     for(int i=1000;i;i--)
12         if (a[x].a[i]!=a[y].a[i])return a[x].a[i]<a[y].a[i];
13     return 0;
14 }
15 int main(){
16     scanf("%d%d%d",&n,&m,&q);
17     for(int i=1;i<=n;i++){
18         scanf("%s",s);
19         for(int j=0;s[j];j++)a[j].a[i]=s[j]-‘0‘; 
20     }
21     for(int i=0;i<m;i++)id[i]=i;
22     sort(id,id+m,cmp);
23     for(int i=0;i<m;i++)rk[id[i]]=i;
24     for(int i=1;i<=q;i++){
25         scanf("%s",s);
26         int x=-1,y=m;
27         for(int j=0;s[j];j++)
28             if (s[j]==‘0‘)x=max(x,rk[j]);
29             else y=min(y,rk[j]);
30         if (x<0)ans=a[id[y]];
31         if (y==m)
32             for(int j=1;j<=n;j++)ans.a[j]=1-a[id[x]].a[j];
33         if ((x>=0)&&(y<m))
34             if (!cmp(id[x],id[y]))memset(ans.a,0,sizeof(ans.a));
35             else
36                 for(int j=1,p=0;j<=1000;j++){
37                     ans.a[j]=a[id[y]].a[j]-p-a[id[x]].a[j];
38                     p=(ans.a[j]<0);
39                     ans.a[j]+=p*2;
40                 }
41         ans.a[0]=0;
42         for(int j=1000;j;j--)ans.a[0]=(ans.a[0]*2+ans.a[j])%mod;
43         printf("%d\n",(ans.a[0]+(y==m))%mod);
44     }
45 }