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\)。

我们发现：

\[ x\ and\ 0=0\\ x\ or\ 1=1 \]

也就是说\(\ and\ 0\)和\(\ or\ 1\)本质上是赋值操作。

然后

\[ x\ and\ 1=x\\ x\ or\ 0=x \]

也就是说\(\ and\ 1\)和\(\ or\ 0\)后上值不变。

然后考虑第\(j\)位，如果它应该为\(1\)，则最后一个赋值操作后第\(j\)位变成了\(1\)。然后我们观察操作序列和第\(j\)列的\(01\)串之间的关系。赋值操作的时候对应位置上的数不同。所以，我们以\(n\)为最高位，设第\(j\)列的数字为\(s_j\),操作序列的数字为\(R\)，则\(R>s_j\)。

反之，则\(R\leq s_j\)。

所以我们将\(m\)列数字排序过后找到上下界就行了。

代码：

#include
    
     #define ll long long#define N 1005#define M 5005using 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]
     
      =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
      
       =rx) cout<<0<<"\n";        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<
       
        <<"\n";        }    }    return 0;}