题解 P4424 【[HNOI/AHOI2018]寻宝游戏】

官方题解 [myy的题解](http://matthew99.blog.uoj.ac/blog/3488) 首先注意到0|1=1|1=1,0&0=1&0=0,也就是说不管前面是什么只要遇到|1和&0后面的结果都是确定的.而&1和|0则不会改变结果 那么对于某一位来说最终结果是1的充要条件就是最后一个&0后面至少要有一个|1.也就是最后一个|1的位置要在最后一个&0后面. 我们可以把操作转化一下,对于第i个操作,如果是|就设为0,&就设为1.这样就转化成了一个长度为n的01串.我们可以观察如果要让某一位为1,这个01串需要满足什么条件.我们从后往前看,如果当前为0,操作串也为0,|0没有任何影响,都为1同理.如果遇到一位不同,操作串为1(&),数字为0则一定非法(因为后面没有|1),反之一定合法. 考虑这个过程我们发现:这实际上就是在比较二进制数的大小!如果后面为高位,那么第i位操作后为1,当且仅当操作串的字典序小于第i位01串.那么满足这一位为1的操作的个数就是这一位01串形成的二进制数. 通过这个结论我们可以很明显的得到算法. 对于每一位形成的01串从大到小进行排序, 对于每一个询问检查是否合法(按照排序后的顺序时候所有0在1后面,为1则小于当前数,为0则大于当前数),直接输出答案(最小的结果为1的01串-最大的结果为0的01串) 代码: ```cpp #include<bits/stdc++.h> #include<tr1/unordered_map> #define For(i,a,b) for(int i=a,i##E=b;i<=i##E;++i) #define rFor(i,a,b) for(int i=a,i##E=b;i>=i##E;--i) #define pb push_back #define pii pair<int,int> #define ft first #define sd second #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; typedef long long LL; const int N=5010; const int inf=0x3f3f3f3f; const int mod=1e9+7; template<typename T>inline bool chkmax(T&A,const T&B){return A<B?1,A=B:0;} template<typename T>inline bool chkmin(T&A,const T&B){return A>B?1,A=B:0;} template<typename T>inline void read(T&x) { x=0;int f=0;char ch=getchar(); while(!isdigit(ch))f|=(ch=='0'),ch=getchar(); while( isdigit(ch))x=x*10+ch-'0',ch=getchar(); x=f?-x:x; } inline void file() { freopen("hunt.in","r",stdin); freopen("hunt.out","w",stdout); } int n,m,Q,len; int a[N]; int num[N],p[N]; char str[N][N],q[N]; inline void Add(int&x,const int&y){x=x+y<mod?x+y:x+y-mod;} inline LL qpow(LL a,LL b) { LL ret=1; for(;b;b>>=1,a=a*a%mod) if(b&1)ret=ret*a%mod; return ret; } struct node{int x[N/30+1],id,ans;}s[N]; inline bool operator<(const node&A,const node&B) { rFor(i,len,0)if(A.x[i]!=B.x[i])return A.x[i]>B.x[i]; return 0; } int main() { file(); read(n),read(m),read(Q); For(i,1,n)scanf("%s",str[i]+1); For(i,1,m) { rFor(j,n,1) { s[i].x[j/30]=(s[i].x[j/30]<<1)|(str[j][i]-'0'); Add(s[i].ans,s[i].ans+(str[j][i]-'0')); } s[i].id=i; } len=n/30; sort(s+1,s+m+1); For(i,1,m)num[s[i].id]=i; s[0].ans=qpow(2,n); while(Q--) { scanf("%s",q+1); For(i,1,m)p[num[i]]=q[i]-'0'; int pos1=0,pos0=0; rFor(i,m,1)if(p[i]){pos1=i;break;} For(i,1,m)if(!p[i]){pos0=i;break;} if(pos0&&pos1&&pos0<pos1)puts("0"); else printf("%d\n",(s[pos1].ans+mod-s[pos1+1].ans)%mod); } return 0; } ```