#include <bits/stdc++.h> using namespace std; using ull = unsigned long long; int n; constexpr ull mod = 1e9 + 7; ull a; vector<ull> dp; vector<ull> sp; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; dp.resize(n + 1); sp.resize(n + 1); dp[0] = 1; sp[0] = 0; for (int i = 1; i <= n; ++i) { cin >> a; sp[i] = sp[i - 1] + a; } for (int i = 0; i < n; ++i) { for (int j = i; j >= 0; --j) { if (!(((sp[i + 1] - sp[j]) % mod) & 1)) { dp[i + 1] += dp[j]; dp[i + 1] %= mod; } } } if (n == 1 && sp[1] & 1) cout << "0\n"; else cout << dp[n] % mod << '\n'; }
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 | #include <bits/stdc++.h> using namespace std; using ull = unsigned long long; int n; constexpr ull mod = 1e9 + 7; ull a; vector<ull> dp; vector<ull> sp; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; dp.resize(n + 1); sp.resize(n + 1); dp[0] = 1; sp[0] = 0; for (int i = 1; i <= n; ++i) { cin >> a; sp[i] = sp[i - 1] + a; } for (int i = 0; i < n; ++i) { for (int j = i; j >= 0; --j) { if (!(((sp[i + 1] - sp[j]) % mod) & 1)) { dp[i + 1] += dp[j]; dp[i + 1] %= mod; } } } if (n == 1 && sp[1] & 1) cout << "0\n"; else cout << dp[n] % mod << '\n'; } |