// #pragma GCC optimize("Ofast") #include <bits/stdc++.h> #define rep(i, p, k) for(int i(p); i < k; ++i) typedef long long int ll; typedef long double ld; template <typename T = int> inline T in() { T x; std::cin >> x; return x; } constexpr int mod = 1e9 + 7; class intm { int val; public: intm() = default; intm(int a) : val{a} {} explicit operator int() {return val;} explicit operator long long() {return val;} friend intm operator+(intm a, intm b){return ((long long)a + (long long)b) % mod;} friend intm operator-(intm a, intm b){return (mod + (long long)a - (long long)b) % mod;} friend intm operator*(intm a, intm b){return ((long long)a * (long long)b) % mod;} friend intm operator-(intm a){return intm(0) - a;} friend intm operator+(intm a){return a;} friend intm operator!(intm a){return !a.val;} intm operator++ () {return *this = *this+1;} intm operator-- () {return *this = *this-1;} friend intm operator^(intm a, long long b) { if(!b)return 1; if(b & 1)return a*(a^(b-1)); intm p(a^(b/2)); return p*p; } intm operator+=(intm b){return *this = *this + b;} intm operator-=(intm b){return *this = *this - b;} intm operator*=(intm b){return *this = *this * b;} intm operator^=(long long b){return *this = *this ^ b;} friend std::ostream& operator<<(std::ostream& out, intm i){return out << i.val;} friend std::istream& operator>>(std::istream& in, intm i){return in >> i.val;} friend bool operator==(intm a, intm b){return a.val == b.val;} friend bool operator!=(intm a, intm b){return a.val != b.val;} friend bool operator<(intm a, intm b){return a.val < b.val;} friend bool operator>(intm a, intm b){return a.val > b.val;} }; class inttree : private std::vector <intm> { int pol; public: inttree(int a) { for(int s(1); ; s *= 2) if(s > 2*a) { resize(s); break; } pol = size()/2; } void add(int g, intm co) { g += pol; do{ std::vector<intm>::operator[](g) += co; g /= 2; } while (g); } intm operator() (int a, int b) const { intm wyn(0); a += pol - 1; b += pol + 1; while(a + 1 != b) { if(!(a & 1))wyn += std::vector<intm>::operator[](a+1); if(b & 1)wyn += std::vector<intm>::operator[](b-1); a >>= 1; b >>= 1; } return wyn; } }; int main() { std::cin.tie(nullptr); std::cout.tie(nullptr); std::ios_base::sync_with_stdio(0); int n(in()); std::vector <int> tab(n+1); rep(i, 1, n+1)std::cin >> tab[i]; std::vector <std::pair <intm, int>> res{{{0, 0}}, {}}; intm sum(0); rep(i, 1, n+1) { sum += tab[i]; res.push_back({sum, i}); } std::sort(res.begin(), res.end()); std::vector <std::pair <bool, int>>id(n+1); rep(j, 0, n+1)id[res[j].second] = {int(res[j].first) % 2, j}; inttree odp[2]{n, n}; odp[0].add(0, 1); rep(i, 1, n+1)odp[id[i].first].add(id[i].second, odp[id[i].first](0, id[i].second) + odp[!id[i].first](id[i].second, n)); std::cout << odp[id[n].first](id[n].second, id[n].second)<<'\n'; 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 | // #pragma GCC optimize("Ofast") #include <bits/stdc++.h> #define rep(i, p, k) for(int i(p); i < k; ++i) typedef long long int ll; typedef long double ld; template <typename T = int> inline T in() { T x; std::cin >> x; return x; } constexpr int mod = 1e9 + 7; class intm { int val; public: intm() = default; intm(int a) : val{a} {} explicit operator int() {return val;} explicit operator long long() {return val;} friend intm operator+(intm a, intm b){return ((long long)a + (long long)b) % mod;} friend intm operator-(intm a, intm b){return (mod + (long long)a - (long long)b) % mod;} friend intm operator*(intm a, intm b){return ((long long)a * (long long)b) % mod;} friend intm operator-(intm a){return intm(0) - a;} friend intm operator+(intm a){return a;} friend intm operator!(intm a){return !a.val;} intm operator++ () {return *this = *this+1;} intm operator-- () {return *this = *this-1;} friend intm operator^(intm a, long long b) { if(!b)return 1; if(b & 1)return a*(a^(b-1)); intm p(a^(b/2)); return p*p; } intm operator+=(intm b){return *this = *this + b;} intm operator-=(intm b){return *this = *this - b;} intm operator*=(intm b){return *this = *this * b;} intm operator^=(long long b){return *this = *this ^ b;} friend std::ostream& operator<<(std::ostream& out, intm i){return out << i.val;} friend std::istream& operator>>(std::istream& in, intm i){return in >> i.val;} friend bool operator==(intm a, intm b){return a.val == b.val;} friend bool operator!=(intm a, intm b){return a.val != b.val;} friend bool operator<(intm a, intm b){return a.val < b.val;} friend bool operator>(intm a, intm b){return a.val > b.val;} }; class inttree : private std::vector <intm> { int pol; public: inttree(int a) { for(int s(1); ; s *= 2) if(s > 2*a) { resize(s); break; } pol = size()/2; } void add(int g, intm co) { g += pol; do{ std::vector<intm>::operator[](g) += co; g /= 2; } while (g); } intm operator() (int a, int b) const { intm wyn(0); a += pol - 1; b += pol + 1; while(a + 1 != b) { if(!(a & 1))wyn += std::vector<intm>::operator[](a+1); if(b & 1)wyn += std::vector<intm>::operator[](b-1); a >>= 1; b >>= 1; } return wyn; } }; int main() { std::cin.tie(nullptr); std::cout.tie(nullptr); std::ios_base::sync_with_stdio(0); int n(in()); std::vector <int> tab(n+1); rep(i, 1, n+1)std::cin >> tab[i]; std::vector <std::pair <intm, int>> res{{{0, 0}}, {}}; intm sum(0); rep(i, 1, n+1) { sum += tab[i]; res.push_back({sum, i}); } std::sort(res.begin(), res.end()); std::vector <std::pair <bool, int>>id(n+1); rep(j, 0, n+1)id[res[j].second] = {int(res[j].first) % 2, j}; inttree odp[2]{n, n}; odp[0].add(0, 1); rep(i, 1, n+1)odp[id[i].first].add(id[i].second, odp[id[i].first](0, id[i].second) + odp[!id[i].first](id[i].second, n)); std::cout << odp[id[n].first](id[n].second, id[n].second)<<'\n'; return 0; } |