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;
}
05-06 03:49