#include<bits/stdc++.h> #define vi vector<int> #define vvi vector<vi> #define pii pair<int, int> #define pll pair<ll, ll> #define vii vector<pii> #define vll vector<pll> #define vb vector<bool> #define vvb vector<vb> #define vl vector<ll> #define endl '\n' #define turbo ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define pb push_back #define ll long long #define f first #define s second #define mid (l+r)/2 #define mide (hi+lo)/(ll)2 using namespace std; ll pot = (ll)1<<(ll)30; ll global_i; ll M = 1000000007; int n; struct tree { ll t[2]; tree* l; tree* r; tree(): l(NULL), r(NULL){t[0] = 0; t[1] = 0;} }; tree* root = new tree(); tree* goL(tree* e) { if(e->l == NULL) e->l = new tree(); return e->l; } tree* goR(tree* e) { if(e->r == NULL) e->r = new tree(); return e->r; } ll get(tree* e, bool senko) { if(e == NULL) return 0; return e->t[senko]; } ll query(ll a, ll b, bool senko, tree* e = root, ll lo = 0, ll hi = pot) { if(b<=a) return 0; if(a == lo and b == hi) return e->t[senko]; ll pom1 = query(a, min(mide, b), senko, goL(e), lo, mide); ll pom2 = query(max(a, mide), b, senko, goR(e), mide, hi); return (pom1+pom2)%M; } void add(ll x, ll val, tree* e = root, ll lo = 0, ll hi = pot) { if(lo+1 == hi) { e->t[x&(ll)1] = (e->t[x&(ll)1] + val)%M; return; } if(lo <= x and x < mide) add(x, val, goL(e), lo, mide); if(mide <= x and x < hi) add(x, val, goR(e), mide, hi); e->t[0] = (get(e->l, 0)+get(e->r, 0))%M; e->t[1] = (get(e->l, 1)+get(e->r, 1))%M; } int main() { turbo cin >> n; global_i = 0; int pom; cin >> pom; add(pom, 1); for(int i = 1; i < n; i++) { ll x; cin >> x; ll poms = (query(global_i, M, global_i%2) + query(0, global_i, (global_i+1)%2))%M; global_i = (global_i-x+M)%M; add((global_i+x)%M,poms); } cout << (query(global_i, M, global_i%2)+query(0, global_i, (global_i+1)%2))%M << endl; }
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 | #include<bits/stdc++.h> #define vi vector<int> #define vvi vector<vi> #define pii pair<int, int> #define pll pair<ll, ll> #define vii vector<pii> #define vll vector<pll> #define vb vector<bool> #define vvb vector<vb> #define vl vector<ll> #define endl '\n' #define turbo ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define pb push_back #define ll long long #define f first #define s second #define mid (l+r)/2 #define mide (hi+lo)/(ll)2 using namespace std; ll pot = (ll)1<<(ll)30; ll global_i; ll M = 1000000007; int n; struct tree { ll t[2]; tree* l; tree* r; tree(): l(NULL), r(NULL){t[0] = 0; t[1] = 0;} }; tree* root = new tree(); tree* goL(tree* e) { if(e->l == NULL) e->l = new tree(); return e->l; } tree* goR(tree* e) { if(e->r == NULL) e->r = new tree(); return e->r; } ll get(tree* e, bool senko) { if(e == NULL) return 0; return e->t[senko]; } ll query(ll a, ll b, bool senko, tree* e = root, ll lo = 0, ll hi = pot) { if(b<=a) return 0; if(a == lo and b == hi) return e->t[senko]; ll pom1 = query(a, min(mide, b), senko, goL(e), lo, mide); ll pom2 = query(max(a, mide), b, senko, goR(e), mide, hi); return (pom1+pom2)%M; } void add(ll x, ll val, tree* e = root, ll lo = 0, ll hi = pot) { if(lo+1 == hi) { e->t[x&(ll)1] = (e->t[x&(ll)1] + val)%M; return; } if(lo <= x and x < mide) add(x, val, goL(e), lo, mide); if(mide <= x and x < hi) add(x, val, goR(e), mide, hi); e->t[0] = (get(e->l, 0)+get(e->r, 0))%M; e->t[1] = (get(e->l, 1)+get(e->r, 1))%M; } int main() { turbo cin >> n; global_i = 0; int pom; cin >> pom; add(pom, 1); for(int i = 1; i < n; i++) { ll x; cin >> x; ll poms = (query(global_i, M, global_i%2) + query(0, global_i, (global_i+1)%2))%M; global_i = (global_i-x+M)%M; add((global_i+x)%M,poms); } cout << (query(global_i, M, global_i%2)+query(0, global_i, (global_i+1)%2))%M << endl; } |