#include <iostream> #include <vector> #include <algorithm> #include <random> #define M 1000000007 using namespace std; vector<int> a; int n; void load_data() { cin >> n; a.resize(n); for (int i = 0; i < n; i++) { int q; cin >> q; a[i] = q; } } void gen_data() { n = 35; n = 5; a.resize(n); for (int i = 0; i < n; i++) { a[i] = rand() % 6; if(rand()%2 == 0){ a[i] += M-6; } } } int bf(int p, long long sum) { int is_g; sum += a[p]; long long s2 = sum % M; is_g = s2%2 == 0; if(p == n-1){ return is_g; } long long res = 0; if(is_g == 1){ res = bf(p+1, 0); } res += bf(p+1, sum); res %= M; return res; } vector<int> res; int sol1(){ res.resize(n); for (int i = 0; i < n; i++) { long long sum = 0; long long com = 0; for (int j = i; j >= 0; j--) { sum += a[j]; long long s2 = sum % M; bool is_g = s2%2 == 0; if(is_g) { if(j-1 < 0) com++; else com += res[j-1]; } } res[i] = com % M; } return res[n-1]; } bool detect_if_small_test(){ long long sum = 0; for (int i = 0; i < n; i++) { sum += a[i]; } return sum < M; } int sol_for_smal(){ long long z = 0, o = 0; if(a[0]%2==0) z++; else o++; for (int i = 1; i < n; i++) { long long zn = 0, on = 0; if(a[i]%2 == 0) { zn = 2*z; on = o; } else{ zn = o; on = 2*z; } z = zn %M; o = on %M; } return z; } void auto_test(){ srand(998); while (true) { gen_data(); int bfs = bf(0,0); int sol1s = sol1(); int smal = sol_for_smal(); if(bfs != sol1s || smal != sol1s){ // cout << "Fail\n"; } cout << detect_if_small_test() << '\n'; sol_for_smal(); } } void run(){ load_data(); if(detect_if_small_test()){ cout << sol_for_smal() << '\n'; } else{ cout << sol1() << '\n'; } } int main() { run(); }
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 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 | #include <iostream> #include <vector> #include <algorithm> #include <random> #define M 1000000007 using namespace std; vector<int> a; int n; void load_data() { cin >> n; a.resize(n); for (int i = 0; i < n; i++) { int q; cin >> q; a[i] = q; } } void gen_data() { n = 35; n = 5; a.resize(n); for (int i = 0; i < n; i++) { a[i] = rand() % 6; if(rand()%2 == 0){ a[i] += M-6; } } } int bf(int p, long long sum) { int is_g; sum += a[p]; long long s2 = sum % M; is_g = s2%2 == 0; if(p == n-1){ return is_g; } long long res = 0; if(is_g == 1){ res = bf(p+1, 0); } res += bf(p+1, sum); res %= M; return res; } vector<int> res; int sol1(){ res.resize(n); for (int i = 0; i < n; i++) { long long sum = 0; long long com = 0; for (int j = i; j >= 0; j--) { sum += a[j]; long long s2 = sum % M; bool is_g = s2%2 == 0; if(is_g) { if(j-1 < 0) com++; else com += res[j-1]; } } res[i] = com % M; } return res[n-1]; } bool detect_if_small_test(){ long long sum = 0; for (int i = 0; i < n; i++) { sum += a[i]; } return sum < M; } int sol_for_smal(){ long long z = 0, o = 0; if(a[0]%2==0) z++; else o++; for (int i = 1; i < n; i++) { long long zn = 0, on = 0; if(a[i]%2 == 0) { zn = 2*z; on = o; } else{ zn = o; on = 2*z; } z = zn %M; o = on %M; } return z; } void auto_test(){ srand(998); while (true) { gen_data(); int bfs = bf(0,0); int sol1s = sol1(); int smal = sol_for_smal(); if(bfs != sol1s || smal != sol1s){ // cout << "Fail\n"; } cout << detect_if_small_test() << '\n'; sol_for_smal(); } } void run(){ load_data(); if(detect_if_small_test()){ cout << sol_for_smal() << '\n'; } else{ cout << sol1() << '\n'; } } int main() { run(); } |