正题
题目链接:https://www.luogu.com.cn/problem/P4424
题目大意
\(n\)个\(m\)位二进制数，开始是一个\(0\)。
然后依次对所有二进制数进行\(n\)次\(and\)或者\(or\)操作。
\(q\)次询问给出二进制数\(r_i\)，要求有多少种操作序列使得操作完后的数是\(r_i\)。
解题思路
一个暴力的想法，每一位考虑可行的序列，然后取一个交。
考虑如果一个位是\(1\)，那么决定它的就是到最后的一个\(or\)上一个\(1\)的一个后缀操作序列。
可以得出一个比较显然的结论就是，把每一位提出来然后翻转得到的一个二进制数\(b\)。如果有\(x<b\)。那么如果\(1\)是\(and\)，\(0\)是\(or\)，那么操作序列\(x\)一定会使得该位变成\(1\)。
那么我们把所有位算出的\(b\)排个序，然后每次快速统计出一个可行的区间就好了。
时间复杂度\(O(mn\log m+q(n+m))\)
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=1100,M=5100,P=1e9+7;
ll n,m,q,ans;
char c[M],s[M];
struct node{
char a[N];
ll id;
}b[M];
bool operator<(node &x,node &y){
for(ll i=1;i<=n;i++)
if(x.a[i]<y.a[i])return 1;
else if(x.a[i]>y.a[i])return 0;
return 0;
}
signed main()
{
scanf("%lld%lld%lld",&n,&m,&q);
for(ll i=1;i<=m;i++)b[i].id=i;
for(ll i=n;i>=1;i--){
scanf("%s",s+1);
for(ll j=1;j<=m;j++)
b[j].a[i]=s[j];
}
for(ll i=1;i<=m;i++)
b[i].a[0]='0';
for(ll i=0;i<=n;i++)
b[m+1].a[i]=b[0].a[i]='0';
b[m+1].a[0]='1';
sort(b+1,b+1+m);
while(q--){
scanf("%s",c+1);
ll rk0=0,rk1=m+1;
for(ll i=m;i>=1;i--)
if(c[b[i].id]=='0'){rk0=i;break;}
for(ll i=1;i<=m;i++)
if(c[b[i].id]=='1'){rk1=i;break;}
if(rk0>rk1)puts("0");
else{
ll ans=0;
for(ll i=0;i<=n;i++)
ans=(ans*2+b[rk1].a[i]-b[rk0].a[i])%P;
printf("%lld\n",(ans+P)%P);
}
}
return 0;
}