目录
显示
题目链接
https://www.luogu.com.cn/problem/P4424
题解
是 myy 的题呢 orz
我们先考虑 \(m=1\) 的情况。
容易发现位运算存在这样的规律:
- \(\vee 1\) 和 \(\wedge 0\) 会直接影响运算结果,前者使得值变为 \(1\),后者使得值变为 \(0\);
- \(\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}
$$
#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; }