北京当地网站 点,域名代理商网站,进入江苏省住房和城乡建设厅网站,网站建设信息安全要求正题
题目链接:https://www.luogu.com.cn/problem/P4424 题目大意 nnn个mmm位二进制数#xff0c;开始是一个000。
然后依次对所有二进制数进行nnn次andandand或者ororor操作。 qqq次询问给出二进制数rir_iri#xff0c;要求有多少种操作序列使得操作完后的数是rir_iri…正题
题目链接:https://www.luogu.com.cn/problem/P4424 题目大意
nnn个mmm位二进制数开始是一个000。
然后依次对所有二进制数进行nnn次andandand或者ororor操作。
qqq次询问给出二进制数rir_iri要求有多少种操作序列使得操作完后的数是rir_iri。 解题思路
一个暴力的想法每一位考虑可行的序列然后取一个交。
考虑如果一个位是111那么决定它的就是到最后的一个ororor上一个111的一个后缀操作序列。
可以得出一个比较显然的结论就是把每一位提出来然后翻转得到的一个二进制数bbb。如果有xbxbxb。那么如果111是andandand000是ororor那么操作序列xxx一定会使得该位变成111。
那么我们把所有位算出的bbb排个序然后每次快速统计出一个可行的区间就好了。
时间复杂度O(mnlogmq(nm))O(mn\log mq(nm))O(mnlogmq(nm)) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1100,M5100,P1e97;
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 i1;in;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 i1;im;i)b[i].idi;for(ll in;i1;i--){scanf(%s,s1);for(ll j1;jm;j)b[j].a[i]s[j];}for(ll i1;im;i)b[i].a[0]0;for(ll i0;in;i)b[m1].a[i]b[0].a[i]0;b[m1].a[0]1;sort(b1,b1m);while(q--){scanf(%s,c1);ll rk00,rk1m1;for(ll im;i1;i--)if(c[b[i].id]0){rk0i;break;}for(ll i1;im;i)if(c[b[i].id]1){rk1i;break;}if(rk0rk1)puts(0);else{ll ans0;for(ll i0;in;i)ans(ans*2b[rk1].a[i]-b[rk0].a[i])%P;printf(%lld\n,(ansP)%P);}}return 0;
}
