#include "bits/stdc++.h" using namespace std; using LL = long long; #define FOR(i, l, r) for(int i = (l); i <= (r); ++i) #define REP(i, n) FOR(i, 0, (n) - 1) template<class T> int size(T &&x) { return int(x.size()); } template<class A, class B> ostream& operator<<(ostream &out, const pair<A, B> &p) { return out << '(' << p.first << ", " << p.second << ')'; } ostream& operator<<(ostream &out, string &str) { for(char c: str) out << c; return out; } template<class T> auto operator<<(ostream &out, T &&x) -> decltype(x.begin(), out) { out << '{'; for(auto it = x.begin(); it != x.end(); ++it) out << *it << (it == prev(x.end()) ? "" : ", "); return out << '}'; } void dump() {} template<class T, class... Args> void dump(T &&x, Args... args) { cerr << x << "; "; dump(args...); } #ifdef DEBUG struct Nl{~Nl(){cerr << '\n';}}; # define debug(x...) cerr << (strcmp(#x, "") ? #x ": " : ""), dump(x), Nl(), cerr << "" #else # define debug(...) 0 && cerr #endif mt19937_64 rng(0); int rd(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); } // end of templates constexpr int mod = int(1e9) + 7; int add(int a, int b) { return a + b >= mod ? a + b - mod : a + b; } int sub(int a, int b) { return a - b < 0 ? a - b + mod : a - b; } void scale(vector<int> &vec) { //utrzymuje parzystość int n = size(vec); vector<pair<int, int>> temp(n); REP(i, n) temp[i] = {vec[i], i}; sort(temp.begin(), temp.end()); vec[temp[0].second] = 0 + (temp[0].first & 1); FOR(i, 1, n - 1) { vec[temp[i].second] = vec[temp[i - 1].second]; if(temp[i].first != temp[i - 1].first) vec[temp[i].second]++; if(vec[temp[i].second] % 2 != temp[i].first % 2) vec[temp[i].second]++; } } struct Tree { vector<int> vec; int sz = 1; Tree(int n) { while((sz *= 2) < n); vec.resize(2 * sz); } void update(int p, int x) { p += sz; vec[p] = add(vec[p], x); while(p /= 2) vec[p] = add(vec[2 * p], vec[2 * p + 1]); } int sum(int l, int r) { l += sz, r += sz; int ret = vec[l]; if(l != r) ret = add(ret, vec[r]); while(l / 2 != r / 2) { if(l % 2 == 0) ret = add(ret, vec[l + 1]); if(r % 2 == 1) ret = add(ret, vec[r - 1]); l /= 2, r /= 2; } return ret; } }; int main() { cin.tie(nullptr)->sync_with_stdio(false); int n; cin >> n; vector<int> vec(n); REP(i, n) cin >> vec[i]; debug(vec); vector<int> pref(n + 1); FOR(i, 1, n) pref[i] = add(pref[i - 1], vec[i - 1]); debug(pref); scale(pref); debug(pref); int mx = *max_element(pref.begin(), pref.end()) + 2; Tree odd(mx), even(mx); even.update(0, 1); int val; FOR(i, 1, n) { int x = pref[i]; debug(x); if(x & 1) { val = add(odd.sum(0, x), even.sum(x + 1, mx - 1)); odd.update(x, val); } else { val = add(even.sum(0, x), odd.sum(x + 1, mx - 1)); even.update(x, val); } debug(val); } cout << val << '\n'; }
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 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 | #include "bits/stdc++.h" using namespace std; using LL = long long; #define FOR(i, l, r) for(int i = (l); i <= (r); ++i) #define REP(i, n) FOR(i, 0, (n) - 1) template<class T> int size(T &&x) { return int(x.size()); } template<class A, class B> ostream& operator<<(ostream &out, const pair<A, B> &p) { return out << '(' << p.first << ", " << p.second << ')'; } ostream& operator<<(ostream &out, string &str) { for(char c: str) out << c; return out; } template<class T> auto operator<<(ostream &out, T &&x) -> decltype(x.begin(), out) { out << '{'; for(auto it = x.begin(); it != x.end(); ++it) out << *it << (it == prev(x.end()) ? "" : ", "); return out << '}'; } void dump() {} template<class T, class... Args> void dump(T &&x, Args... args) { cerr << x << "; "; dump(args...); } #ifdef DEBUG struct Nl{~Nl(){cerr << '\n';}}; # define debug(x...) cerr << (strcmp(#x, "") ? #x ": " : ""), dump(x), Nl(), cerr << "" #else # define debug(...) 0 && cerr #endif mt19937_64 rng(0); int rd(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); } // end of templates constexpr int mod = int(1e9) + 7; int add(int a, int b) { return a + b >= mod ? a + b - mod : a + b; } int sub(int a, int b) { return a - b < 0 ? a - b + mod : a - b; } void scale(vector<int> &vec) { //utrzymuje parzystość int n = size(vec); vector<pair<int, int>> temp(n); REP(i, n) temp[i] = {vec[i], i}; sort(temp.begin(), temp.end()); vec[temp[0].second] = 0 + (temp[0].first & 1); FOR(i, 1, n - 1) { vec[temp[i].second] = vec[temp[i - 1].second]; if(temp[i].first != temp[i - 1].first) vec[temp[i].second]++; if(vec[temp[i].second] % 2 != temp[i].first % 2) vec[temp[i].second]++; } } struct Tree { vector<int> vec; int sz = 1; Tree(int n) { while((sz *= 2) < n); vec.resize(2 * sz); } void update(int p, int x) { p += sz; vec[p] = add(vec[p], x); while(p /= 2) vec[p] = add(vec[2 * p], vec[2 * p + 1]); } int sum(int l, int r) { l += sz, r += sz; int ret = vec[l]; if(l != r) ret = add(ret, vec[r]); while(l / 2 != r / 2) { if(l % 2 == 0) ret = add(ret, vec[l + 1]); if(r % 2 == 1) ret = add(ret, vec[r - 1]); l /= 2, r /= 2; } return ret; } }; int main() { cin.tie(nullptr)->sync_with_stdio(false); int n; cin >> n; vector<int> vec(n); REP(i, n) cin >> vec[i]; debug(vec); vector<int> pref(n + 1); FOR(i, 1, n) pref[i] = add(pref[i - 1], vec[i - 1]); debug(pref); scale(pref); debug(pref); int mx = *max_element(pref.begin(), pref.end()) + 2; Tree odd(mx), even(mx); even.update(0, 1); int val; FOR(i, 1, n) { int x = pref[i]; debug(x); if(x & 1) { val = add(odd.sum(0, x), even.sum(x + 1, mx - 1)); odd.update(x, val); } else { val = add(even.sum(0, x), odd.sum(x + 1, mx - 1)); even.update(x, val); } debug(val); } cout << val << '\n'; } |