Loj #2494. 「AHOI / HNOI2018」寻宝游戏
题目描述
某大学每年都会有一次 Mystery Hunt 的活动，玩家需要根据设置的线索解谜，找到宝藏的位置，前一年获胜的队伍可以获得这一年出题的机会。
作为新生的你对这个活动非常感兴趣。你每天都要从西向东经过教学楼一条很长的走廊，这条走廊是如此的长，以至于它被人戏称为 infinite corridor。一次，你经过这条走廊的时，注意到在走廊的墙壁上隐藏着 (n) 个等长的二进制的数字，长度均为 (m)。你从西向东将这些数字记录了下来，形成一个含有 (n) 个数的二进制数组 (a_1, a_2, ..., a_n)。很快，在最新的一期 Voo Doo 杂志上，你发现了 (q) 个长度也为 (m) 的二进制串 (r_1, r_2, ..., r_q)。聪明的你很快发现了这些数字的含义。保持数组 (a_1, a_2, ..., a_n) 的元素顺序不变,你可以在它们之间插入 (wedge)（按位与运算）或者 (vee)（按位或运算）两种二进制运算符。例如：(11011 wedge 00111=00011,11011 vee 00111=11111)。
你需要插入恰好 (n) 个运算符,相邻两个数之间恰好一个，在第一个数的左边还有一个。如果我们在第一个运算符的左边补入一个 (0)，这就形成了一个运算式，我们可以计算它的值。与往常一样,运算顺序是从左往右。有趣的是,出题人已经告诉你这个值的可能的集合——Voo Doo 杂志里的那一些二进制数 (r_1, r_2, ..., r_q)，而解谜的方法,就是对 (r_1, r_2, ..., r_q) 中的每一个值 (r_i)，分别计算出有多少种方法填入这 (n) 个运算符,使得这个运算式的值是 (r_i) 。然而，infinite corridor 真的很长，这意味着数据范围可能非常大。因此，答案也可能非常大，但是你发现由于谜题的特殊性，你只需要求答案模 (1000000007)（(10^9 + 7)，一个质数）的值。
输入格式
第一行三个数 (n, m, q)，含义如题所述。
接下来 (n) 行，其中第 (i) 行有一个长度为 (m) 的二进制串，左边是最高位，表示 (a_i)。
接下来 (q) 行，其中第 (i) 行有一个长度为 (m) 的二进制串，左边是最高位，表示 (r_i)。
输出格式
输出 (q) 行，每行一个数,其中第 (i) 行表示对应于 (r_i) 的答案。
数据范围与提示
对于 (10\%) 的数据，(n le 20, m le 30)，(q = 1)
对于另外 (20\%) 的数据，(n le 1000)，(m le 16)
对于另外 (40\%) 的数据，(n le 500)，(m le 1000)
对于 (100\%) 的数据，(1 le n le 1000)，(1 le m le 5000)，(1 le q le 1000)
(\)
(myy)的题就是神仙啊！
首先我们对每一位单独考虑，再将(m)位的一起考虑。
我们将操作序列也定义为一个(01)串。如果是(and)操作，则为(1)，否则为(0)。
我们发现：
也就是说( and 0)和( or 1)本质上是赋值操作。
然后
也就是说( and 1)和( or 0)后上值不变。
然后考虑第(j)位，如果它应该为(1)，则最后一个赋值操作后第(j)位变成了(1)。然后我们观察操作序列和第(j)列的(01)串之间的关系。赋值操作的时候对应位置上的数不同。所以，我们以(n)为最高位，设第(j)列的数字为(s_j),操作序列的数字为(R)，则(R>s_j)。
反之，则(Rleq s_j)。
所以我们将(m)列数字排序过后找到上下界就行了。
代码：
#include<bits/stdc++.h>
#define ll long long
#define N 1005
#define M 5005
using namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}
const ll mod=1e9+7;
int n,m,q;
char a[N][M],r[M];
ll pw2[M];
int len;
const ll maxx=1<<30;
int rk[M];
struct node {
int id;
ll val[50];
bool operator <(const node &x)const {
for(int i=len;i>=1;i--) if(val[i]!=x.val[i]) return val[i]<x.val[i];
return id<x.id;
}
}s[M];
node operator -(node a,node b) {
for(int i=1;i<=len;i++) {
if(a.val[i]<b.val[i]) {
a.val[i+1]--;
a.val[i]+=maxx;
}
a.val[i]-=b.val[i];
}
return a;
}
ll bin[N];
int main() {
n=Get(),m=Get(),q=Get();
pw2[0]=1;
for(int i=1;i<=n;i++) pw2[i]=pw2[i-1]*2%mod;
for(int i=1;i<=n;i++) scanf("%s",a[i]+1);
len=(n-1)/30+1;
for(int i=1;i<=m;i++) s[i].id=i;
for(int j=n;j>=1;j--) {
int now=(j-1)/30+1;
for(int i=1;i<=m;i++) {
s[i].val[now]=(s[i].val[now]<<1)|(a[j][i]-'0');
}
}
sort(s+1,s+1+m);
for(int i=1;i<=m;i++) rk[s[i].id]=i;
for(int i=1;i<=n;i++) {
int now=(i-1)/30+1;
s[m+1].val[now]=(s[m+1].val[now]<<1)|1;
}
for(int i=1;i<len;i++) bin[i]=i*30;
bin[len]=bin[len-1]+(n-1)%30+1;
s[0].id=0,s[m+1].id=m+1;
int tim=0;
while(q--) {
scanf("%s",r+1);
int lx=0,rx=m+1;
for(int i=1;i<=m;i++) {
if(r[i]=='1') rx=min(rx,rk[i]);
else lx=max(lx,rk[i]);
}
if(lx>=rx) cout<<0<<"
";
else {
ll ans=0;
node c=s[rx]-s[lx];
for(int i=1;i<=len;i++) (ans+=c.val[i]*pw2[bin[i-1]])%=mod;
if(rx==m+1) ans=(ans+1)%mod;
cout<<ans<<"
";
}
}
return 0;
}