#include <bits/stdc++.h> #define qio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define debug(x) cerr<<#x<<" "<<x<<endl #define ll long long #define st first #define nd second using namespace std; int n, t, pref[300003], a[300003], mod = 1e9 + 7, x, temp, base = 1, tree[3][1500006], ile, nie, res, sum; map <int, int> M; vector <int> V; void baza(int v, int a, int b, int l, int r, int par) { if (a > r || b<l || l>r) return; if (a >= l && b <= r) { sum = (sum + tree[par][v]) % mod; return; } int mid = (a + b) / 2; baza(v * 2, a, mid, l, r, par); baza(v * 2 + 1, mid + 1, b, l, r, par); } int main() { qio; cin >> n; M[0] = 1; for (int i = 1; i <= n; i++) { cin >> a[i]; pref[i] = (pref[i - 1] + a[i]) % mod; M[pref[i]] = 1; } ile = 0; for (auto it : M) { ile++; M[it.st] = ile; V.push_back(it.st); } while (base < ile) base *= 2; temp = base; while (temp > 0) { tree[0][temp] = 1; temp /= 2; } for (int i = 1; i <= n; i++) { auto it = lower_bound(V.begin(), V.end(), pref[i]); x = it - V.begin(); sum = 0; baza(1, 0, base - 1, 0, x, pref[i] % 2); baza(1, 0, base - 1, x + 1, base - 1, 1 - (pref[i] % 2)); temp = x + base; while (temp > 0) { tree[pref[i] % 2][temp] = (tree[pref[i] % 2][temp] + sum) % mod; temp /= 2; } } cout << sum << endl; /*if (pref[n] < mod) { if (nie % 2 == 1) { cout << 0 << endl; return 0; } nie = 0; for (int i = 1; i <= n; i++) { if (nie == 0 && a[i] % 2 == 0) ile++; else if (nie == 0 && a[i] % 2 == 1) nie++; else if (nie == 1 && a[i] % 2 == 1) { nie = 0; ile++; } } res = 1; for (int i = 1; i < ile; i++) { res = (res * 2) % mod; } cout << res << endl; } else { dp[0] = 1; for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { if (((pref[i] - pref[j]) % mod) % 2 == 0) dp[i] = (dp[i] + dp[j]) % mod; } } cout << dp[n] << endl; }*/ }
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 | #include <bits/stdc++.h> #define qio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define debug(x) cerr<<#x<<" "<<x<<endl #define ll long long #define st first #define nd second using namespace std; int n, t, pref[300003], a[300003], mod = 1e9 + 7, x, temp, base = 1, tree[3][1500006], ile, nie, res, sum; map <int, int> M; vector <int> V; void baza(int v, int a, int b, int l, int r, int par) { if (a > r || b<l || l>r) return; if (a >= l && b <= r) { sum = (sum + tree[par][v]) % mod; return; } int mid = (a + b) / 2; baza(v * 2, a, mid, l, r, par); baza(v * 2 + 1, mid + 1, b, l, r, par); } int main() { qio; cin >> n; M[0] = 1; for (int i = 1; i <= n; i++) { cin >> a[i]; pref[i] = (pref[i - 1] + a[i]) % mod; M[pref[i]] = 1; } ile = 0; for (auto it : M) { ile++; M[it.st] = ile; V.push_back(it.st); } while (base < ile) base *= 2; temp = base; while (temp > 0) { tree[0][temp] = 1; temp /= 2; } for (int i = 1; i <= n; i++) { auto it = lower_bound(V.begin(), V.end(), pref[i]); x = it - V.begin(); sum = 0; baza(1, 0, base - 1, 0, x, pref[i] % 2); baza(1, 0, base - 1, x + 1, base - 1, 1 - (pref[i] % 2)); temp = x + base; while (temp > 0) { tree[pref[i] % 2][temp] = (tree[pref[i] % 2][temp] + sum) % mod; temp /= 2; } } cout << sum << endl; /*if (pref[n] < mod) { if (nie % 2 == 1) { cout << 0 << endl; return 0; } nie = 0; for (int i = 1; i <= n; i++) { if (nie == 0 && a[i] % 2 == 0) ile++; else if (nie == 0 && a[i] % 2 == 1) nie++; else if (nie == 1 && a[i] % 2 == 1) { nie = 0; ile++; } } res = 1; for (int i = 1; i < ile; i++) { res = (res * 2) % mod; } cout << res << endl; } else { dp[0] = 1; for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { if (((pref[i] - pref[j]) % mod) % 2 == 0) dp[i] = (dp[i] + dp[j]) % mod; } } cout << dp[n] << endl; }*/ } |