[HNOI2018]寻宝游戏

Description:

给出\(n\)个长为\(m\)的01串，第0个为0，同时给出\(q\)个询问串，每次向其中添加\(n\)个\(\&\)或\(|\)符号，求使这些串按顺序运算得到询问串的方案数

Hint:

\(n<=1000,m<=5000,q<=1000\)

Solution:

按位考虑

把这些串按位拆成m个长为n的串

发现只有\(|1\)和\(\&0\)会改变答案

且每一位最终为1的充要条件是最后一个\(|1\)在\(\&0\)后

为0则反之

再将操作序列也看成01串

\(|\)为\(0,\&\)为\(1\),

则问题转化为原串与操作串的字典序大小关系

每次找到操作串的上界和下界，相减便是答案

#include<bits/stdc++.h>

using namespace std;

const int mxn=5e3+5,mod=1e9+7;

int n,m,q;

int t[mxn][mxn],s[mxn],rk[mxn],p[mxn];

char c[mxn];

int cmp(int a,int b)

{

	for(int i=1;i<=n;++i)

		if(t[a][i]!=t[b][i]) return t[a][i]<t[b][i];

	return 0;

}

void init()

{

	p[0]=1;

	for(int i=1;i<=mxn-5;++i) p[i]=1ll*p[i-1]*2%mod;

	for(int i=1;i<=m;++i) reverse(t[i]+1,t[i]+n+1);

	for(int i=1;i<=m;++i) rk[i]=i;

	sort(rk+1,rk+m+1,cmp);

	for(int i=1;i<=m;++i)

		for(int j=1;j<=n;++j)

			s[i]=(s[i]+1ll*t[rk[i]][j]*p[n-j])%mod; //预处理，按字典序排序后每次能按顺序扫

	s[m+1]=p[n];

}

void solve()

{

	for(int i=1;i<=q;++i) {

		scanf("%s",c+1);

		int st=0,ed=m+1;

		for(int i=m;i>=1;--i) if(c[rk[i]]=='0') {st=i;break;}

		for(int i=1;i<=m;++i) if(c[rk[i]]=='1') {ed=i;break;} //找上下界

		printf("%d\n",ed>=st?(s[ed]-s[st]+mod)%mod:0);

	}

}

int main()

{

	scanf("%d%d%d",&n,&m,&q);

	for(int i=1;i<=n;++i) {

		scanf("%s",c+1);

		for(int j=1;j<=m;++j)

			t[j][i]=c[j]-'0';

	}

	init();

	solve();

	return 0;

}