#include <bits/stdc++.h> using namespace std; int n,ite; long long a[300005],pre[300005],dp[300005], t0[1200005],t1[1200005],iii[300005]; pair<long long,int>pr[300005]; long long sump,sumn; const int p = 1000000007; void u0(int v,int tl,int tr,int it,int ii) { if(tl == tr && tl == it) { t0[v] = dp[ii]; return; } if(it < tl || tr < it) return; int tm = (tr + tl) / 2; u0(2 * v,tl,tm,it,ii); u0(2 * v + 1,tm + 1,tr,it,ii); t0[v] = t0[2 * v] + t0[2 * v + 1]; t0[v] %= p; } long long q0(int v,int tl,int tr,int l,int r) { if(r < l) return 0; if(r < tl || tr < l) return 0; if(l <= tl && tr <= r) return t0[v]; int tm = (tl + tr) / 2; return (q0(2 * v,tl,tm,l,r) + q0(2 * v + 1,tm + 1,tr,l,r)) % p; } void u1(int v,int tl,int tr,int it,int ii) { if(tl == tr && tl == it) { t1[v] = dp[ii]; return; } if(it < tl || tr < it) return; int tm = (tr + tl) / 2; u1(2 * v,tl,tm,it,ii); u1(2 * v + 1,tm + 1,tr,it,ii); t1[v] = t1[2 * v] + t1[2 * v + 1]; t1[v] %= p; } long long q1(int v,int tl,int tr,int l,int r) { if(r < l) return 0; if(r < tl || tr < l) return 0; if(l <= tl && tr <= r) return t1[v]; int tm = (tl + tr) / 2; return (q1(2 * v,tl,tm,l,r) + q1(2 * v + 1,tm + 1,tr,l,r)) % p; } int bs(long long k) { int l,r,mid,ans; ans = -1; l = 0;r = n; while(l <= r) { mid = (r + l) / 2; if(pr[mid].first <= k) { ans = mid; l = mid + 1; } else r = mid - 1; } return ans; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; pre[i] = pre[i - 1] + a[i]; pre[i] %= p; pr[i] = {pre[i],i}; } pr[0] = {0,0}; sort(pr,pr + n + 1); for(int i=0;i<=n;i++) iii[pr[i].second] = i; dp[0] = 1; u0(1,0,n,0,0); for(int i=1;i<=n;i++) { ite = bs(pre[i]); if(pre[i] % 2 == 0) { dp[i] = q0(1,0,n,0,ite) + q1(1,0,n,ite + 1,n); dp[i] %= p; //cout<<i<<" "<<ite<<" "<<q0(1,0,n,0,ite)<<" "<<q1(1,0,n,ite + 1,n)<<endl; u0(1,0,n,iii[i],i); } else { dp[i] = q1(1,0,n,0,ite) + q0(1,0,n,ite + 1,n); dp[i] %= p; //cout<<i<<" "<<q1(1,0,n,0,ite)<<" "<<q0(1,0,n,ite + 1,n)<<endl; u1(1,0,n,iii[i],i); } } //for(int i=1;i<=n;i++) cout<<dp[n]<<endl; 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 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 | #include <bits/stdc++.h> using namespace std; int n,ite; long long a[300005],pre[300005],dp[300005], t0[1200005],t1[1200005],iii[300005]; pair<long long,int>pr[300005]; long long sump,sumn; const int p = 1000000007; void u0(int v,int tl,int tr,int it,int ii) { if(tl == tr && tl == it) { t0[v] = dp[ii]; return; } if(it < tl || tr < it) return; int tm = (tr + tl) / 2; u0(2 * v,tl,tm,it,ii); u0(2 * v + 1,tm + 1,tr,it,ii); t0[v] = t0[2 * v] + t0[2 * v + 1]; t0[v] %= p; } long long q0(int v,int tl,int tr,int l,int r) { if(r < l) return 0; if(r < tl || tr < l) return 0; if(l <= tl && tr <= r) return t0[v]; int tm = (tl + tr) / 2; return (q0(2 * v,tl,tm,l,r) + q0(2 * v + 1,tm + 1,tr,l,r)) % p; } void u1(int v,int tl,int tr,int it,int ii) { if(tl == tr && tl == it) { t1[v] = dp[ii]; return; } if(it < tl || tr < it) return; int tm = (tr + tl) / 2; u1(2 * v,tl,tm,it,ii); u1(2 * v + 1,tm + 1,tr,it,ii); t1[v] = t1[2 * v] + t1[2 * v + 1]; t1[v] %= p; } long long q1(int v,int tl,int tr,int l,int r) { if(r < l) return 0; if(r < tl || tr < l) return 0; if(l <= tl && tr <= r) return t1[v]; int tm = (tl + tr) / 2; return (q1(2 * v,tl,tm,l,r) + q1(2 * v + 1,tm + 1,tr,l,r)) % p; } int bs(long long k) { int l,r,mid,ans; ans = -1; l = 0;r = n; while(l <= r) { mid = (r + l) / 2; if(pr[mid].first <= k) { ans = mid; l = mid + 1; } else r = mid - 1; } return ans; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; pre[i] = pre[i - 1] + a[i]; pre[i] %= p; pr[i] = {pre[i],i}; } pr[0] = {0,0}; sort(pr,pr + n + 1); for(int i=0;i<=n;i++) iii[pr[i].second] = i; dp[0] = 1; u0(1,0,n,0,0); for(int i=1;i<=n;i++) { ite = bs(pre[i]); if(pre[i] % 2 == 0) { dp[i] = q0(1,0,n,0,ite) + q1(1,0,n,ite + 1,n); dp[i] %= p; //cout<<i<<" "<<ite<<" "<<q0(1,0,n,0,ite)<<" "<<q1(1,0,n,ite + 1,n)<<endl; u0(1,0,n,iii[i],i); } else { dp[i] = q1(1,0,n,0,ite) + q0(1,0,n,ite + 1,n); dp[i] %= p; //cout<<i<<" "<<q1(1,0,n,0,ite)<<" "<<q0(1,0,n,ite + 1,n)<<endl; u1(1,0,n,iii[i],i); } } //for(int i=1;i<=n;i++) cout<<dp[n]<<endl; return 0; } |