#include <bits/stdc++.h> using namespace std; using LL = long long; const int MAXN = 300005, MOD = 1000000007, BASE = 524288; int n; int t[MAXN]; pair<int, int> permHlp[MAXN]; int perm[MAXN]; int add(int a, int b) { return (LL)(a + b) % MOD; } int tree[2][MAXN * 4]; void update(int par, int w, int val) { w += BASE - 1; tree[par][w] = add(tree[par][w], val); while (w != 1) { w /= 2; tree[par][w] = add(tree[par][w * 2], tree[par][w * 2 + 1]); } } int queryLess(int par, int w) { w += BASE - 1; int ret = tree[par][w]; while (w != 1) { if (w % 2 == 1) { ret = add(ret, tree[par][w - 1]); } w /= 2; } return ret; } int queryGreat(int par, int w) { w += BASE - 1; // int ret = tree[par][w]; int ret = 0; while (w != 1) { if (w % 2 == 0) { ret = add(ret, tree[par][w + 1]); } w /= 2; } return ret; } int getDpValue(int i) { int val = t[i]; int valNode = perm[i]; int ret = 0; if (val % 2 == 0) { int less = queryLess(0, valNode); int more = queryGreat(1, valNode); ret = add(less, more); update(0, valNode, ret); } else { int less = queryLess(1, valNode); int more = queryGreat(0, valNode); ret = add(less, more); update(1, valNode, ret); } return ret; } int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d", &t[i]); t[i] = add(t[i], t[i - 1]); permHlp[i] = {t[i], i}; } sort(permHlp + 1, permHlp + 1 + n); int act = 1; for (int i = 1; i <= n; ++i) { perm[permHlp[i].second] = act; while (i < n && permHlp[i].first == permHlp[i + 1].first) { i++; perm[permHlp[i].second] = act; } ++act; } update(0, 1, 1); int ret = 0; for (int i = 1; i <= n; ++i) { ret = getDpValue(i); // printf("%d :: %d\n", i, ret); } printf("%d\n", ret); }
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 | #include <bits/stdc++.h> using namespace std; using LL = long long; const int MAXN = 300005, MOD = 1000000007, BASE = 524288; int n; int t[MAXN]; pair<int, int> permHlp[MAXN]; int perm[MAXN]; int add(int a, int b) { return (LL)(a + b) % MOD; } int tree[2][MAXN * 4]; void update(int par, int w, int val) { w += BASE - 1; tree[par][w] = add(tree[par][w], val); while (w != 1) { w /= 2; tree[par][w] = add(tree[par][w * 2], tree[par][w * 2 + 1]); } } int queryLess(int par, int w) { w += BASE - 1; int ret = tree[par][w]; while (w != 1) { if (w % 2 == 1) { ret = add(ret, tree[par][w - 1]); } w /= 2; } return ret; } int queryGreat(int par, int w) { w += BASE - 1; // int ret = tree[par][w]; int ret = 0; while (w != 1) { if (w % 2 == 0) { ret = add(ret, tree[par][w + 1]); } w /= 2; } return ret; } int getDpValue(int i) { int val = t[i]; int valNode = perm[i]; int ret = 0; if (val % 2 == 0) { int less = queryLess(0, valNode); int more = queryGreat(1, valNode); ret = add(less, more); update(0, valNode, ret); } else { int less = queryLess(1, valNode); int more = queryGreat(0, valNode); ret = add(less, more); update(1, valNode, ret); } return ret; } int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d", &t[i]); t[i] = add(t[i], t[i - 1]); permHlp[i] = {t[i], i}; } sort(permHlp + 1, permHlp + 1 + n); int act = 1; for (int i = 1; i <= n; ++i) { perm[permHlp[i].second] = act; while (i < n && permHlp[i].first == permHlp[i + 1].first) { i++; perm[permHlp[i].second] = act; } ++act; } update(0, 1, 1); int ret = 0; for (int i = 1; i <= n; ++i) { ret = getDpValue(i); // printf("%d :: %d\n", i, ret); } printf("%d\n", ret); } |