#include <bits/stdc++.h> #include <random> #define ll long long int #define pb push_back #define st first #define nd second #define pii pair<int,int> #define mp make_pair #define pll pair<long long,long long> #define ld long double #define ull unsigned long long using namespace std; const int mod = 1e9 + 7; const int nax = 3e5 + 5; ll a[nax]; set<int> UNIQ; ll pref[nax]; int n; struct FenwickTree { vector<int> bit; // binary indexed tree int n; FenwickTree(int n) { this->n = n; bit.assign(n, 0); } FenwickTree(vector<int> a) : FenwickTree(a.size()) { for (size_t i = 0; i < a.size(); i++) add(i, a[i]); } int sum(int r) { int ret = 0; for (; r >= 0; r = (r & (r + 1)) - 1){ ret += bit[r]; if(ret >= mod) ret -= mod; } return ret; } int sum(int l, int r) { if(l > r) return 0; int res = sum(r) - sum(l - 1); if(res < 0) res += mod; return res; } void add(int idx, int delta) { for (; idx < n; idx = idx | (idx + 1)){ bit[idx] += delta; if(bit[idx] >= mod) bit[idx] -= mod; } } }; vector<int> u; int get(int x){ return (int)(lower_bound(u.begin(), u.end(), x) - u.begin()); } ll dp[nax]; void solve(){ cin >> n; for(int i=1;i<=n;i++) cin >> a[i]; for(int i=1;i<=n;i++) pref[i] = pref[i - 1] + a[i]; for(int i=0;i<=n;i++) UNIQ.insert(pref[i] % mod); UNIQ.insert(mod - 1); for(int x : UNIQ) u.pb(x); FenwickTree treeNP(nax), treeP(nax); treeP.add(get(0), 1); for(int i=1;i<=n;i++){ ll cur = pref[i] % mod; int s1 = 0; int s2 = 0; if(cur & 1){ s1 = treeNP.sum(0, get(cur)); s2 = treeP.sum(get(cur), get(mod - 1)); } else{ s1 = treeP.sum(0, get(cur)); s2 = treeNP.sum(get(cur), get(mod - 1)); } dp[i] = (s1 + s2) % mod; if(cur & 1) treeNP.add(get(cur), dp[i]); else treeP.add(get(cur), dp[i]); } cout << dp[n]; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int tt = 1; // cin >> tt; while(tt--) solve(); 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 102 103 104 105 106 | #include <bits/stdc++.h> #include <random> #define ll long long int #define pb push_back #define st first #define nd second #define pii pair<int,int> #define mp make_pair #define pll pair<long long,long long> #define ld long double #define ull unsigned long long using namespace std; const int mod = 1e9 + 7; const int nax = 3e5 + 5; ll a[nax]; set<int> UNIQ; ll pref[nax]; int n; struct FenwickTree { vector<int> bit; // binary indexed tree int n; FenwickTree(int n) { this->n = n; bit.assign(n, 0); } FenwickTree(vector<int> a) : FenwickTree(a.size()) { for (size_t i = 0; i < a.size(); i++) add(i, a[i]); } int sum(int r) { int ret = 0; for (; r >= 0; r = (r & (r + 1)) - 1){ ret += bit[r]; if(ret >= mod) ret -= mod; } return ret; } int sum(int l, int r) { if(l > r) return 0; int res = sum(r) - sum(l - 1); if(res < 0) res += mod; return res; } void add(int idx, int delta) { for (; idx < n; idx = idx | (idx + 1)){ bit[idx] += delta; if(bit[idx] >= mod) bit[idx] -= mod; } } }; vector<int> u; int get(int x){ return (int)(lower_bound(u.begin(), u.end(), x) - u.begin()); } ll dp[nax]; void solve(){ cin >> n; for(int i=1;i<=n;i++) cin >> a[i]; for(int i=1;i<=n;i++) pref[i] = pref[i - 1] + a[i]; for(int i=0;i<=n;i++) UNIQ.insert(pref[i] % mod); UNIQ.insert(mod - 1); for(int x : UNIQ) u.pb(x); FenwickTree treeNP(nax), treeP(nax); treeP.add(get(0), 1); for(int i=1;i<=n;i++){ ll cur = pref[i] % mod; int s1 = 0; int s2 = 0; if(cur & 1){ s1 = treeNP.sum(0, get(cur)); s2 = treeP.sum(get(cur), get(mod - 1)); } else{ s1 = treeP.sum(0, get(cur)); s2 = treeNP.sum(get(cur), get(mod - 1)); } dp[i] = (s1 + s2) % mod; if(cur & 1) treeNP.add(get(cur), dp[i]); else treeP.add(get(cur), dp[i]); } cout << dp[n]; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int tt = 1; // cin >> tt; while(tt--) solve(); return 0; } |