/* Zadanie: Mopadulo Autor: Tomasz Kwiatkowski */ #include <bits/stdc++.h> #define fi first #define se second #define pb push_back using namespace std; typedef long long ll; const int MAXN = 3e5 + 7; const int MOD = (int)1e9 + 7; struct Node { Node *left, *right; long long sum; int a, b; // [a, b) Node (int A, int B) : a(A), b(B) { sum = 0; left = NULL; right = NULL; } bool is_leaf() { return a == b-1; } void insert(int ind, int val) { if ((ind < a) || (ind >= b)) return; if (is_leaf()) { sum = (sum + val) % MOD; return; } if (left == NULL) { left = new Node(a, (a + b) / 2); right = new Node((a + b) / 2, b); } left->insert(ind, val); right->insert(ind, val); sum = (left->sum + right->sum) % MOD; } // [l, r] int get_sum(int l, int r) { if ((r < a) || (l >= b)) return 0; if (((l <= a) && (b <= r)) || is_leaf()) return sum; if (left == NULL) { left = new Node(a, (a + b) / 2); right = new Node((a + b) / 2, b); } return (left->get_sum(l, r) + right->get_sum(l, r)) % MOD; } }; int main() { ios_base::sync_with_stdio(0), cin.tie(0); int n; cin >> n; vector<int> arr(n); for (auto& a : arr) cin >> a; Node *evenRoot = new Node(0, 1<<30); Node *oddRoot = new Node(0, 1<<30); evenRoot->insert(0, 1); int sum = 0; int ans = 0; for (auto a : arr) { sum = (sum + a) % MOD; if (sum & 1) { int res = (evenRoot->get_sum(sum, MOD) + oddRoot->get_sum(0, sum)) % MOD; oddRoot->insert(sum, res); ans = res; } else { int res = (evenRoot->get_sum(0, sum) + oddRoot->get_sum(sum, MOD)) % MOD; evenRoot->insert(sum, res); ans = res; } } cout << ans << '\n'; 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 101 | /* Zadanie: Mopadulo Autor: Tomasz Kwiatkowski */ #include <bits/stdc++.h> #define fi first #define se second #define pb push_back using namespace std; typedef long long ll; const int MAXN = 3e5 + 7; const int MOD = (int)1e9 + 7; struct Node { Node *left, *right; long long sum; int a, b; // [a, b) Node (int A, int B) : a(A), b(B) { sum = 0; left = NULL; right = NULL; } bool is_leaf() { return a == b-1; } void insert(int ind, int val) { if ((ind < a) || (ind >= b)) return; if (is_leaf()) { sum = (sum + val) % MOD; return; } if (left == NULL) { left = new Node(a, (a + b) / 2); right = new Node((a + b) / 2, b); } left->insert(ind, val); right->insert(ind, val); sum = (left->sum + right->sum) % MOD; } // [l, r] int get_sum(int l, int r) { if ((r < a) || (l >= b)) return 0; if (((l <= a) && (b <= r)) || is_leaf()) return sum; if (left == NULL) { left = new Node(a, (a + b) / 2); right = new Node((a + b) / 2, b); } return (left->get_sum(l, r) + right->get_sum(l, r)) % MOD; } }; int main() { ios_base::sync_with_stdio(0), cin.tie(0); int n; cin >> n; vector<int> arr(n); for (auto& a : arr) cin >> a; Node *evenRoot = new Node(0, 1<<30); Node *oddRoot = new Node(0, 1<<30); evenRoot->insert(0, 1); int sum = 0; int ans = 0; for (auto a : arr) { sum = (sum + a) % MOD; if (sum & 1) { int res = (evenRoot->get_sum(sum, MOD) + oddRoot->get_sum(0, sum)) % MOD; oddRoot->insert(sum, res); ans = res; } else { int res = (evenRoot->get_sum(0, sum) + oddRoot->get_sum(sum, MOD)) % MOD; evenRoot->insert(sum, res); ans = res; } } cout << ans << '\n'; return 0; } |