#include<bits/stdc++.h> using namespace std; const int mod = 1e9 + 7; const int MAXN = 1e6; typedef long long ll; unordered_set <bitset<MAXN>> used; void gen(bitset<MAXN> a, int n, int r, ll &res, int i, int changed) { if(changed == r) return; if(i == n) return; gen(a, n, r, res, i+1, changed); a.flip(i); if(used.find(a) == used.end()) { used.insert(a); res = (res+1)%mod; } gen(a, n, r, res, i+1, changed+1); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; //set<bitset<MAXN>> used; ll res = 0; bitset<MAXN> back1; bitset<MAXN> back2; int rB1; int rB2; ll resB1; ll resB2; for(int t=0; t<3; ++t) { int r; cin >> r; bitset<MAXN> a; for(int i=0; i<n; ++i) { char tmp; cin >> tmp; if(tmp&1) a.flip(i); } if(t == 0) { rB1 = r; back1 = a; } if(t == 1) { rB2 = r; back2 = a; } if(t == 1 && r == rB1 && back1 == a) { res = (res + resB1)%mod; continue; } if(t == 2) { if(r == rB1 && back1 == a) { res = (res + resB1)%mod; continue; } else if(r == rB2 && back2 == a) { res = (res + resB2)%mod; continue; } } ll cr = 0; bitset<MAXN> b; if(used.find(a) == used.end()) used.insert(a), ++cr; gen(a, n, r, cr, 0, 0); if(t == 1) resB1 = cr; if(t == 2) resB2 = cr; res = (res + cr)%mod; } cout << res << '\n'; return 0; } /* 3 1 000 1 100 0 111 5 2 10110 0 11010 1 00000 */
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 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 | #include<bits/stdc++.h> using namespace std; const int mod = 1e9 + 7; const int MAXN = 1e6; typedef long long ll; unordered_set <bitset<MAXN>> used; void gen(bitset<MAXN> a, int n, int r, ll &res, int i, int changed) { if(changed == r) return; if(i == n) return; gen(a, n, r, res, i+1, changed); a.flip(i); if(used.find(a) == used.end()) { used.insert(a); res = (res+1)%mod; } gen(a, n, r, res, i+1, changed+1); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; //set<bitset<MAXN>> used; ll res = 0; bitset<MAXN> back1; bitset<MAXN> back2; int rB1; int rB2; ll resB1; ll resB2; for(int t=0; t<3; ++t) { int r; cin >> r; bitset<MAXN> a; for(int i=0; i<n; ++i) { char tmp; cin >> tmp; if(tmp&1) a.flip(i); } if(t == 0) { rB1 = r; back1 = a; } if(t == 1) { rB2 = r; back2 = a; } if(t == 1 && r == rB1 && back1 == a) { res = (res + resB1)%mod; continue; } if(t == 2) { if(r == rB1 && back1 == a) { res = (res + resB1)%mod; continue; } else if(r == rB2 && back2 == a) { res = (res + resB2)%mod; continue; } } ll cr = 0; bitset<MAXN> b; if(used.find(a) == used.end()) used.insert(a), ++cr; gen(a, n, r, cr, 0, 0); if(t == 1) resB1 = cr; if(t == 2) resB2 = cr; res = (res + cr)%mod; } cout << res << '\n'; return 0; } /* 3 1 000 1 100 0 111 5 2 10110 0 11010 1 00000 */ |