// clang-format off #include <bits/stdc++.h> using namespace std; #define ALL(x) (x).begin(), (x).end() template<class C> void mini(C &a5, C b5) { a5 = min(a5, b5); } template<class C> void maxi(C &a5, C b5) { a5 = max(a5, b5); } #ifdef LOCAL const bool debug = true; #else const bool debug = false; #define cerr if (true) {} else cout #endif // clang-format on #define int long long #define double long double const int INF = 1e18; const int mod = 1e9 + 7; const int baza = 1 << 19; struct Tree { vector<int> drz; Tree() : drz(2 * baza) {} void add(int gdzie, int ile) { gdzie += baza; while (gdzie) { drz[gdzie] += ile; drz[gdzie] %= mod; gdzie >>= 1; } } int czytaj(int pyt_pocz, int pyt_kon) { pyt_kon--; pyt_pocz += baza; pyt_kon += baza; int res = 0; while (pyt_pocz < pyt_kon) { if (pyt_pocz & 1) { res += drz[pyt_pocz]; } if ((pyt_kon & 1) == 0) { res += drz[pyt_kon]; } pyt_pocz = (pyt_pocz + 1) >> 1; pyt_kon = (pyt_kon - 1) >> 1; } if (pyt_pocz == pyt_kon) res += drz[pyt_pocz]; return res % mod; } } even, odd; int tab[baza]; int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; set<int> s = {0}; unordered_map<int, int> mapa; int sum = 0; for (int i = 0; i < n; i++) { cin >> tab[i]; sum += mod - tab[i]; sum %= mod; s.insert(sum); } int li = 0; for (int i : s) { mapa[i] = li++; } sum = 0; int res = 0; even.add(mapa[0], 1); for (int i = 0; i < n; i++) { sum += mod - tab[i]; sum %= mod; int ms = mapa[sum]; res = 0; if (sum & 1) { res += odd.czytaj(ms, baza); res += even.czytaj(0, ms); } else { res += even.czytaj(ms, baza); res += odd.czytaj(0, ms); } res %= mod; if (sum & 1) { odd.add(ms, res); } else { even.add(ms, res); } } cout << res << endl; return 0; }/* 4 1000000006 1 5 1000000004 */
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 | // clang-format off #include <bits/stdc++.h> using namespace std; #define ALL(x) (x).begin(), (x).end() template<class C> void mini(C &a5, C b5) { a5 = min(a5, b5); } template<class C> void maxi(C &a5, C b5) { a5 = max(a5, b5); } #ifdef LOCAL const bool debug = true; #else const bool debug = false; #define cerr if (true) {} else cout #endif // clang-format on #define int long long #define double long double const int INF = 1e18; const int mod = 1e9 + 7; const int baza = 1 << 19; struct Tree { vector<int> drz; Tree() : drz(2 * baza) {} void add(int gdzie, int ile) { gdzie += baza; while (gdzie) { drz[gdzie] += ile; drz[gdzie] %= mod; gdzie >>= 1; } } int czytaj(int pyt_pocz, int pyt_kon) { pyt_kon--; pyt_pocz += baza; pyt_kon += baza; int res = 0; while (pyt_pocz < pyt_kon) { if (pyt_pocz & 1) { res += drz[pyt_pocz]; } if ((pyt_kon & 1) == 0) { res += drz[pyt_kon]; } pyt_pocz = (pyt_pocz + 1) >> 1; pyt_kon = (pyt_kon - 1) >> 1; } if (pyt_pocz == pyt_kon) res += drz[pyt_pocz]; return res % mod; } } even, odd; int tab[baza]; int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; set<int> s = {0}; unordered_map<int, int> mapa; int sum = 0; for (int i = 0; i < n; i++) { cin >> tab[i]; sum += mod - tab[i]; sum %= mod; s.insert(sum); } int li = 0; for (int i : s) { mapa[i] = li++; } sum = 0; int res = 0; even.add(mapa[0], 1); for (int i = 0; i < n; i++) { sum += mod - tab[i]; sum %= mod; int ms = mapa[sum]; res = 0; if (sum & 1) { res += odd.czytaj(ms, baza); res += even.czytaj(0, ms); } else { res += even.czytaj(ms, baza); res += odd.czytaj(0, ms); } res %= mod; if (sum & 1) { odd.add(ms, res); } else { even.add(ms, res); } } cout << res << endl; return 0; }/* 4 1000000006 1 5 1000000004 */ |