#include <iostream> #include <string> #include <algorithm> #include <vector> using namespace std; typedef pair<int, vector<bool> > clause; int s2n(string &s, int p) { int r = 0; while (p < s.size() && '0' <= s[p] && s[p] <= '9') { r = r * 10 + (s[p] - '0'); p++; } return r; } int mod = (int)10e9 + 7; vector<int> pow2; vector<clause> t; int func(int s, int e, vector<int> &v) { if (!v.size()) return pow2[e - s + 1]; if (s > e) return 0; vector<int> v0; vector<int> v1; int f = 0; for (int i = 0; i < v.size(); i++) { f = min(f, t[v[i]].first); if (t[v[i]].first > s) { v0.push_back(v[i]); v1.push_back(v[i]); } else if (t[v[i]].first + t[v[i]].second.size() <= s) { return 0; } else { int k = s - t[v[i]].first; if (t[v[i]].second[k]) { v0.push_back(v[i]); } else { v1.push_back(v[i]); } } } if (f > s) { v0.clear(); v1.clear(); return ((long long)pow2[f - s] * func(f, e, v)) % mod; } else { return (func(s+1, e, v0) + func(s+1, e, v1)) % mod; } } int main() { ios_base::sync_with_stdio(0); int n; string inp; getline(cin, inp); n = s2n(inp, 0); getline(cin, inp); pow2.resize(n+1); int i = 0; vector<pair<int, bool> > cr; while (i < inp.size()) { if (inp[i] == '(') { cr.clear(); } else if (inp[i] == 'x') { cr.push_back(pair<int, bool>(s2n(inp, i+1), inp[i-1] != '~')); } else if (inp[i] == ')') { clause c; sort(cr.begin(), cr.end()); c.first = cr[0].first; for (int j = 0; j < cr.size(); j++) { c.second.push_back(cr[j].second); } t.push_back(c); } i++; } pow2[0] = 1; for (int i = 1; i <= n; i++) pow2[i] = (pow2[i-1] << 1) % mod; vector<int> v; for (int i = 0; i < t.size(); i++) v.push_back(i); cout << func(1, n, v) << endl; 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 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 | #include <iostream> #include <string> #include <algorithm> #include <vector> using namespace std; typedef pair<int, vector<bool> > clause; int s2n(string &s, int p) { int r = 0; while (p < s.size() && '0' <= s[p] && s[p] <= '9') { r = r * 10 + (s[p] - '0'); p++; } return r; } int mod = (int)10e9 + 7; vector<int> pow2; vector<clause> t; int func(int s, int e, vector<int> &v) { if (!v.size()) return pow2[e - s + 1]; if (s > e) return 0; vector<int> v0; vector<int> v1; int f = 0; for (int i = 0; i < v.size(); i++) { f = min(f, t[v[i]].first); if (t[v[i]].first > s) { v0.push_back(v[i]); v1.push_back(v[i]); } else if (t[v[i]].first + t[v[i]].second.size() <= s) { return 0; } else { int k = s - t[v[i]].first; if (t[v[i]].second[k]) { v0.push_back(v[i]); } else { v1.push_back(v[i]); } } } if (f > s) { v0.clear(); v1.clear(); return ((long long)pow2[f - s] * func(f, e, v)) % mod; } else { return (func(s+1, e, v0) + func(s+1, e, v1)) % mod; } } int main() { ios_base::sync_with_stdio(0); int n; string inp; getline(cin, inp); n = s2n(inp, 0); getline(cin, inp); pow2.resize(n+1); int i = 0; vector<pair<int, bool> > cr; while (i < inp.size()) { if (inp[i] == '(') { cr.clear(); } else if (inp[i] == 'x') { cr.push_back(pair<int, bool>(s2n(inp, i+1), inp[i-1] != '~')); } else if (inp[i] == ')') { clause c; sort(cr.begin(), cr.end()); c.first = cr[0].first; for (int j = 0; j < cr.size(); j++) { c.second.push_back(cr[j].second); } t.push_back(c); } i++; } pow2[0] = 1; for (int i = 1; i <= n; i++) pow2[i] = (pow2[i-1] << 1) % mod; vector<int> v; for (int i = 0; i < t.size(); i++) v.push_back(i); cout << func(1, n, v) << endl; return 0; } |