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

Kelin

2018-04-25 17:58:30

Solution

## [题意](https://blog.csdn.net/BeNoble_/article/details/80083151) 给你$n$个长度为$m$的$01$串 你可以在每个串前面加一个运算符$\land$或$\lor,$分别表示$and$和$or$运算 每次询问一个长度为$m$的$01$串$,$问有多少总操作序列能得到这个串 --- ## 题解 因为是二进制数$,$所以考虑按位处理($i$表示第$i$个数字$,j$表示第$j$位) $1.$ >$0\lor1=1,1\lor1=1$ >$0\land0=0,1\land0=0$ 也就是说如果第$j$位是$0$且$i$前面的运算符是$\land,$那么不管前面是什么最后的运算结果都确定了是$0$(另外一种情况同理) $2.$ >$0\lor0=0,1\lor0=1$ >$0\land1=0,1\land1=1$ 也就是说如果第$j$位是$0$且$i$前面的运算符是$\lor,$那么不管前面是什么最后的运算结果都不会发生改变(另外一种情况同理) 考虑把操作序列转化成$01$序列$(\lor\to0,\land\to1)$ 可以观察到 >如果$i$前面的运算符和第$j$位相同那么运算结果就不会改变 >否则的话运算结果也是可以直接得出的 设最后一位是最高位 把第$j$位的$01$串提出来得到一个长度是$n$的二进制数$x$ 因为要使得第$j$位运算结果是$1$则最后一个$\lor1$操作的位置一定要在$\land0$后面 转化一下就是就要求$x\gt$**操作串** $e.g$ >$ x=1011,op=0011,x\gt op$ >$0\lor 1\lor 0\land 1\land 1=1$ >$ x=1011,op=1011,x\le op$ >$0\land 1\lor 0\land 1\land 1=0$ 那么这道题就成功的转化为一个比大小的题目了 每一位按照其二进制数的值排序 判断一下每一位二进制数和$op$的大小关系 如果有解最后可以得到$x\le op\lt y,$那么方案数就是$y-x$ ``` #include<bits/stdc++.h> #define fp(i,a,b) for(register int i=a,I=b+1;i<I;++i) #define fd(i,a,b) for(register int i=a,I=b-1;i>I;--i) #define go(u) for(register int i=fi[u],v=e[i].to;i;v=e[i=e[i].nx].to) #define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;} template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;} using namespace std; const int N=5005,P=1e9+7; typedef int arr[N]; int n,m,q,c[2];arr a,b,s,t,Mi;char p[N]; inline int pls(int a,int b){return a+=b,a<P?a:a-P;} inline int sub(int a,int b){return a-=b,a<0?a+P:a;} int main(){ #ifndef ONLINE_JUDGE file("s"); #endif scanf("%d%d%d\n",&n,&m,&q); Mi[1]=1;fp(i,2,n+1)Mi[i]=(Mi[i-1]<<1)%P; fp(i,1,m)a[i]=i; fp(i,1,n){ gets(p+1);c[0]=0,c[1]=m; fp(j,1,m)p[j]=='1'?s[j]=pls(s[j],Mi[i]):++c[0]; fd(j,m,1)b[c[p[a[j]]-48]--]=a[j];swap(a,b); } fp(i,1,m)t[i]=s[a[i]]; register int up,dw;t[m+1]=Mi[n+1]; while(q--){ gets(p+1);up=m+1,dw=0; fd(i,m,1)if(p[a[i]]=='0'){dw=i;break;} fp(i,1,m)if(p[a[i]]=='1'){up=i;break;} printf("%d\n",up<dw?0:sub(t[up],t[dw])); } return 0; } ```