#include <bits/stdc++.h> #define ff first #define ss second using namespace std; int n, r1, r2, r3; string s1, s2, s3; long long ss1, ss2, ss3; map<long long, short> mapa; map<long long, bool> odw,odw2; queue<pair<int,int> > q; void bfs(int v, int odl, int r) { odw[v]=1; odw2[v]=1; q.push({v,odl}); if (odl<r) while (!q.empty()) { v=q.front().ff; odl=q.front().ss; //cout<<v<<" "; q.pop(); for (int i=1; i<(1<<n); i*=2) { if (v&i) { if (!odw[v&(((1<<n)-1)^i)]) { odw[v&(((1<<n)-1)^i)]=1; odw2[v&(((1<<n)-1)^i)]=1; if (odl+1<r) q.push({v&(((1<<n)-1)^i),odl+1}); } } else { if (!odw[v|i]) { odw[v|i]=1; odw2[v|i]=1; if (odl+1<r) q.push({v|i,odl+1}); } } } } else q.pop(); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>n>>r1>>s1>>r2>>s2>>r3>>s3; for (int i=0; i<n; i++) { ss1*=2; if (s1[i]=='1') ss1++; } for (int i=0; i<n; i++) { ss2*=2; if (s2[i]=='1') ss2++; } for (int i=0; i<n; i++) { ss3*=2; if (s3[i]=='1') ss3++; } //cout<<ss1<<" "<<ss2<<" "<<ss3<<"\n"; bfs(ss1, 0, r1); odw.clear(); bfs(ss2, 0, r2); odw.clear(); bfs(ss3, 0, r3); cout<<odw2.size(); return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 | #include <bits/stdc++.h> #define ff first #define ss second using namespace std; int n, r1, r2, r3; string s1, s2, s3; long long ss1, ss2, ss3; map<long long, short> mapa; map<long long, bool> odw,odw2; queue<pair<int,int> > q; void bfs(int v, int odl, int r) { odw[v]=1; odw2[v]=1; q.push({v,odl}); if (odl<r) while (!q.empty()) { v=q.front().ff; odl=q.front().ss; //cout<<v<<" "; q.pop(); for (int i=1; i<(1<<n); i*=2) { if (v&i) { if (!odw[v&(((1<<n)-1)^i)]) { odw[v&(((1<<n)-1)^i)]=1; odw2[v&(((1<<n)-1)^i)]=1; if (odl+1<r) q.push({v&(((1<<n)-1)^i),odl+1}); } } else { if (!odw[v|i]) { odw[v|i]=1; odw2[v|i]=1; if (odl+1<r) q.push({v|i,odl+1}); } } } } else q.pop(); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>n>>r1>>s1>>r2>>s2>>r3>>s3; for (int i=0; i<n; i++) { ss1*=2; if (s1[i]=='1') ss1++; } for (int i=0; i<n; i++) { ss2*=2; if (s2[i]=='1') ss2++; } for (int i=0; i<n; i++) { ss3*=2; if (s3[i]=='1') ss3++; } //cout<<ss1<<" "<<ss2<<" "<<ss3<<"\n"; bfs(ss1, 0, r1); odw.clear(); bfs(ss2, 0, r2); odw.clear(); bfs(ss3, 0, r3); cout<<odw2.size(); return 0; } |