题解 P4424 【[HNOI/AHOI2018]寻宝游戏】
StudyingFather
2020-04-19 17:38:01
是 myy 的题呢 orz
我们先考虑 $m=1$ 的情况。
容易发现位运算存在这样的规律：
1. $\vee 1$ 和 $\wedge 0$ 会直接影响运算结果，前者使得值变为 $1$，后者使得值变为 $0$；
2. $\vee 0$ 和 $\wedge 1$ 对结果没有影响。
由上面两个结论可以知道，运算最后结果为 $1$，当且仅当存在至少一个 $\vee 1$ 操作，且最后一个 $\vee 1$ 操作在 $\wedge 0$ 操作之前。
看起来似乎还是不太好办？我们转化一下。
设操作序列中 $\vee=0$，$\wedge=1$。
同时我们设数字序列从下往上看得到的数为 $x$，操作序列从下往上看得到的数为 $y$，
这样我们可以转化条件：运算最后结果为 $1$，当且仅当 $x \gt y$。
感性理解一下，从高位向低位相同的位都不影响结果，而对于第一个不同的位，$x$ 对应的位为 $1$，$y$ 对应的位为 $0$ 时，意味着我们在这个位上执行了一次 $\vee 1$ 操作，根据前面的性质，易知这种情况下运算结果为 $1$，反之同理。
最后解集一定是这两个不等式之一：$x \gt y$（该位是 $1$） 或者是 $x \leq y$（该位是 $0$）。
这样我们就解决了 $m=1$ 的情况。
对于多个位的情况，我们需要将各个位的结果合并。
说白了就是解这样一个不等式组：
$$
\begin{cases}
x \gt a_1\\
x \leq a_2\\
x \leq a_3\\
x \gt a_4\\
\vdots
\end{cases}
$$
```cpp
// Problem : P4424 [HNOI/AHOI2018]寻宝游戏
// Contest : Luogu
// URL : https://www.luogu.com.cn/problem/P4424
// Author : StudyingFather
// Site : https://studyingfather.com
// Memory Limit : 500 MB
// Time Limit : 1000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)
#include <iostream>
#include <string>
#include <algorithm>
#define MOD 1000000007
using namespace std;
struct node
{
string s;
int id;
bool operator<(const node&a)const
{
return s>a.s||(s==a.s&&id<a.id);
}
}p[5005];
string a[1005];
long long res[5005];
int main()
{
ios::sync_with_stdio(false);
int n,m,q;
cin>>n>>m>>q;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=0;i<m;i++)
{
p[i].id=i;
for(int j=n;j;j--)
{
a[j][i]-='0';
res[i]=(res[i]*2+a[j][i])%MOD;
p[i].s.push_back(a[j][i]);
}
}
p[m].id=m;
p[m+1].id=m+1;
for(int j=n;j;j--)
{
res[m]=(res[m]*2+1)%MOD;
p[m].s.push_back(1);
}
res[m]++;
sort(p,p+m+1);
while(q--)
{
string str;
cin>>str;
int l=0,r=m+1;
for(int i=m;i;i--)
if(str[p[i].id]=='1')
{
l=i;
break;
}
for(int i=0;i<=m;i++)
if(str[p[i].id]=='0')
{
r=i;
break;
}
cout<<(l>r?0:(res[p[l].id]-res[p[r].id]+MOD)%MOD)<<endl;
}
return 0;
}
```