#include <iostream> #include <vector> constexpr long long mod = 1000 * 1000 * 1000 + 7; std::vector<long long> get_combinations(int n, long long m) { std::vector<long long> result(n + 1, 0); result[2] = (m - 1) % mod; for (int i = 3; i <= n; ++i) { result[i] = (result[i - 1] * m) % mod; } return result; } std::vector<long long> get_powers(int n, long long m) { std::vector<long long> result(n + 1, 0); result[2] = m % mod; for (int i = 3; i <= n; ++i) { result[i] = (result[i - 1] * m) % mod; } return result; } long long solution() { long long n, m; std::cin >> n >> m; if (n < 2) return 0; std::vector<long long> combinations = get_combinations(n, m); std::vector<long long> powers = get_powers(n, m); std::vector<long long> dp(n + 1, 0); dp[2] = m % mod; if (n >= 3) { dp[3] = (m * m) % mod; } for (int i = 4; i <= n; ++i) { for (int j = i - 2; j >= 2; --j) { dp[i] += (dp[j] * combinations[i - j]) % mod; dp[i] = dp[i] % mod; } dp[i] += powers[i]; dp[i] = 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 44 45 46 47 48 49 50 51 52 53 54 55 | #include <iostream> #include <vector> constexpr long long mod = 1000 * 1000 * 1000 + 7; std::vector<long long> get_combinations(int n, long long m) { std::vector<long long> result(n + 1, 0); result[2] = (m - 1) % mod; for (int i = 3; i <= n; ++i) { result[i] = (result[i - 1] * m) % mod; } return result; } std::vector<long long> get_powers(int n, long long m) { std::vector<long long> result(n + 1, 0); result[2] = m % mod; for (int i = 3; i <= n; ++i) { result[i] = (result[i - 1] * m) % mod; } return result; } long long solution() { long long n, m; std::cin >> n >> m; if (n < 2) return 0; std::vector<long long> combinations = get_combinations(n, m); std::vector<long long> powers = get_powers(n, m); std::vector<long long> dp(n + 1, 0); dp[2] = m % mod; if (n >= 3) { dp[3] = (m * m) % mod; } for (int i = 4; i <= n; ++i) { for (int j = i - 2; j >= 2; --j) { dp[i] += (dp[j] * combinations[i - j]) % mod; dp[i] = dp[i] % mod; } dp[i] += powers[i]; dp[i] = dp[i] % mod; } return dp[n]; } int main() { std::cout << solution() << "\n"; return 0; } |