#include <bits/stdc++.h> using namespace std; int n, p; vector<vector<int>> tree; vector<int> pos; vector<int> sorted; vector<int> v; const int MOD = 1e9+7; int sum(int b, int e, bool val, int l = 0, int r = (1 << p), int x = 1) { if (l >= r || l >= e || r <= b) return 0; if (l >= b && r <= e) return tree[x][val]; int mid = (l + r + 1) >> 1; int ret = sum(b, e, val, l, mid, x << 1) + sum(b, e, val, mid, r, (x << 1) + 1); if (ret >= MOD) ret -= MOD; return ret; } void insert(int val, int pos, bool parity) { pos += (1 << p); while (pos) { tree[pos][parity] += val; if (tree[pos][parity] >= MOD) tree[pos][parity] -= MOD; pos >>= 1; } } int getDp(int i) { int mid = upper_bound(sorted.begin(), sorted.end(), v[i]) - sorted.begin(); return sum(0, mid, v[i] & 1) + sum(mid, n, !(v[i] & 1)); } void solve() { insert(1, pos[0], 0); int dp = 1; for (int i = 1; i < n; ++i) { dp = getDp(i); if (dp >= MOD) dp -= MOD; insert(dp, pos[i], v[i] & 1); } cout << dp << '\n'; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n; ++n; v.resize(n); v[0] = 0; for (int i = 1; i < n; ++i) { cin >> v[i]; v[i] += v[i - 1]; if (v[i] >= MOD) v[i] -= MOD; } pos.resize(n); for (int i = 0; i < n; ++i) pos[i] = i; sort(pos.begin(), pos.end(), [&](const int &a, const int &b) { return v[a] < v[b]; }); vector<int> tmp(n); for (int i = 0; i < n; ++i) tmp[pos[i]] = i; pos = tmp; sorted.resize(n); for (int i = 0; i < n; ++i) sorted[pos[i]] = v[i]; p = 0; while ((1 << p) < n) ++p; tree.assign(1 << (p + 1), vector<int>(2, 0)); solve(); }
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 | #include <bits/stdc++.h> using namespace std; int n, p; vector<vector<int>> tree; vector<int> pos; vector<int> sorted; vector<int> v; const int MOD = 1e9+7; int sum(int b, int e, bool val, int l = 0, int r = (1 << p), int x = 1) { if (l >= r || l >= e || r <= b) return 0; if (l >= b && r <= e) return tree[x][val]; int mid = (l + r + 1) >> 1; int ret = sum(b, e, val, l, mid, x << 1) + sum(b, e, val, mid, r, (x << 1) + 1); if (ret >= MOD) ret -= MOD; return ret; } void insert(int val, int pos, bool parity) { pos += (1 << p); while (pos) { tree[pos][parity] += val; if (tree[pos][parity] >= MOD) tree[pos][parity] -= MOD; pos >>= 1; } } int getDp(int i) { int mid = upper_bound(sorted.begin(), sorted.end(), v[i]) - sorted.begin(); return sum(0, mid, v[i] & 1) + sum(mid, n, !(v[i] & 1)); } void solve() { insert(1, pos[0], 0); int dp = 1; for (int i = 1; i < n; ++i) { dp = getDp(i); if (dp >= MOD) dp -= MOD; insert(dp, pos[i], v[i] & 1); } cout << dp << '\n'; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n; ++n; v.resize(n); v[0] = 0; for (int i = 1; i < n; ++i) { cin >> v[i]; v[i] += v[i - 1]; if (v[i] >= MOD) v[i] -= MOD; } pos.resize(n); for (int i = 0; i < n; ++i) pos[i] = i; sort(pos.begin(), pos.end(), [&](const int &a, const int &b) { return v[a] < v[b]; }); vector<int> tmp(n); for (int i = 0; i < n; ++i) tmp[pos[i]] = i; pos = tmp; sorted.resize(n); for (int i = 0; i < n; ++i) sorted[pos[i]] = v[i]; p = 0; while ((1 << p) < n) ++p; tree.assign(1 << (p + 1), vector<int>(2, 0)); solve(); } |