#include <bits/stdc++.h> using namespace std; const int MOD = 1000000007; const bool EVEN = 0, ODD = 1; void solve_small(vector<int>& r, int n) { bool p; pair<int, int> v({0, 1}); vector<int> t({0, 0}); for (int i = 1; i <= n; i++) { p = (r[i] - r[i - 1]) & 1; v.first = v.second; v.second = (t[p] + (p == EVEN) * v.second) % MOD; t[p] = (t[p] + v.first) % MOD; } cout << v.second << endl; } void bruteforce(vector<int>& r, int n) { vector<int> a(n + 1, 0); a[0] = 1; for (int i = 1; i <= n; i++) { for (int j = i - 1; j >= 0; j--) { if(abs(r[i] - r[j]) % 2 == EVEN) { if(r[i] >= r[j]) a[i] = (a[i] + a[j]) % MOD; } else if(r[i] < r[j]) a[i] = (a[i] + a[j]) % MOD; } } cout << a.back() << endl; } int main(int argc, char* argv[]) { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; bool small = true; cin >> n; vector<int> r(n + 1, 0); for(int i = 1; i <= n; i++) { cin >> r[i]; r[i] += r[i - 1]; if(r[i] > MOD) small = false; r[i] %= MOD; } if (small) solve_small(r, n); else bruteforce(r, 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 | #include <bits/stdc++.h> using namespace std; const int MOD = 1000000007; const bool EVEN = 0, ODD = 1; void solve_small(vector<int>& r, int n) { bool p; pair<int, int> v({0, 1}); vector<int> t({0, 0}); for (int i = 1; i <= n; i++) { p = (r[i] - r[i - 1]) & 1; v.first = v.second; v.second = (t[p] + (p == EVEN) * v.second) % MOD; t[p] = (t[p] + v.first) % MOD; } cout << v.second << endl; } void bruteforce(vector<int>& r, int n) { vector<int> a(n + 1, 0); a[0] = 1; for (int i = 1; i <= n; i++) { for (int j = i - 1; j >= 0; j--) { if(abs(r[i] - r[j]) % 2 == EVEN) { if(r[i] >= r[j]) a[i] = (a[i] + a[j]) % MOD; } else if(r[i] < r[j]) a[i] = (a[i] + a[j]) % MOD; } } cout << a.back() << endl; } int main(int argc, char* argv[]) { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; bool small = true; cin >> n; vector<int> r(n + 1, 0); for(int i = 1; i <= n; i++) { cin >> r[i]; r[i] += r[i - 1]; if(r[i] > MOD) small = false; r[i] %= MOD; } if (small) solve_small(r, n); else bruteforce(r, n); return 0; } |