#include <iostream> #include <vector> constexpr long long mod = 1000 * 1000 * 1000 + 7; int solution() { int n; std::cin >> n; std::vector<long long> tab(n + 1); for (int i = 1; i <= n; ++i) { std::cin >> tab[i]; } tab[0] = 0; // sumy prefiksowe for (int i = 2; i <= n; ++i) { tab[i] += tab[i - 1]; tab[i] %= mod; } // dp[i] = ile jest dobrych podziałów dla podciągu a_0, ..., a_i std::vector<long long> dp(n + 1, 0); dp[0] = 1; int tmp; for (int i = 1; i <= n; ++i) { for (int j = i; j >= 1; --j) { tmp = tab[i] - tab[j - 1]; if (tmp < 0) tmp += mod; if (tmp % 2 == 0) { dp[i] += dp[j - 1]; dp[i] %= mod; } } } return dp[n]; } int main() { std::cout << solution() << "\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 | #include <iostream> #include <vector> constexpr long long mod = 1000 * 1000 * 1000 + 7; int solution() { int n; std::cin >> n; std::vector<long long> tab(n + 1); for (int i = 1; i <= n; ++i) { std::cin >> tab[i]; } tab[0] = 0; // sumy prefiksowe for (int i = 2; i <= n; ++i) { tab[i] += tab[i - 1]; tab[i] %= mod; } // dp[i] = ile jest dobrych podziałów dla podciągu a_0, ..., a_i std::vector<long long> dp(n + 1, 0); dp[0] = 1; int tmp; for (int i = 1; i <= n; ++i) { for (int j = i; j >= 1; --j) { tmp = tab[i] - tab[j - 1]; if (tmp < 0) tmp += mod; if (tmp % 2 == 0) { dp[i] += dp[j - 1]; dp[i] %= mod; } } } return dp[n]; } int main() { std::cout << solution() << "\n"; return 0; } |