正題

題目鏈接:https://www.luogu.com.cn/problem/P4424

---

題目大意

$n$個$m$位二進制數，開始是一個$0$。

然后依次對所有二進制數進行$n$次$and$或者$or$操作。

$q$次詢問給出二進制數$r_i$，要求有多少種操作序列使得操作完后的數是$r_i$。

---

解題思路

一個暴力的想法，每一位考慮可行的序列，然后取一個交。

考慮如果一個位是$1$，那么決定它的就是到最后的一個$or$上一個$1$的一個后綴操作序列。

可以得出一個比較顯然的結論就是，把每一位提出來然后翻轉得到的一個二進制數$b$。如果有$x<b$。那么如果$1$是$and$，$0$是$or$，那么操作序列$x$一定會使得該位變成$1$。

那么我們把所有位算出的$b$排個序，然后每次快速統計出一個可行的區間就好了。

時間復雜度$O(mn\log m+q(n+m))$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=1100,M=5100,P=1e9+7; ll n,m,q,ans; char c[M],s[M]; struct node{char a[N];ll id; }b[M]; bool operator<(node &x,node &y){for(ll i=1;i<=n;i++)if(x.a[i]<y.a[i])return 1;else if(x.a[i]>y.a[i])return 0;return 0; } signed main() {scanf("%lld%lld%lld",&n,&m,&q);for(ll i=1;i<=m;i++)b[i].id=i;for(ll i=n;i>=1;i--){scanf("%s",s+1);for(ll j=1;j<=m;j++)b[j].a[i]=s[j];}for(ll i=1;i<=m;i++)b[i].a[0]='0';for(ll i=0;i<=n;i++)b[m+1].a[i]=b[0].a[i]='0';b[m+1].a[0]='1';sort(b+1,b+1+m);while(q--){scanf("%s",c+1);ll rk0=0,rk1=m+1;for(ll i=m;i>=1;i--)if(c[b[i].id]=='0'){rk0=i;break;}for(ll i=1;i<=m;i++)if(c[b[i].id]=='1'){rk1=i;break;}if(rk0>rk1)puts("0");else{ll ans=0;for(ll i=0;i<=n;i++)ans=(ans*2+b[rk1].a[i]-b[rk0].a[i])%P;printf("%lld\n",(ans+P)%P);}}return 0; }

總結

以上是生活随笔為你收集整理的P4424-[HNOI/AHOI2018]寻宝游戏【结论】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。