#include <bits/stdc++.h> using namespace std; typedef long long lld; constexpr int INF = 1e9+7; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<vector<int> > dp(n, vector<int> (n / 2 + 1, 0)); dp[1][1] = m; for (int i = 2; i < n; ++i) for (int k = 1; k <= n / 2; ++k) dp[i][k] = ((lld)dp[i - 1][k] * (lld)m + (lld)dp[i - 2][k - 1] * (lld)(m - k + 1)) % (lld)INF; // 2*10^18 int sum = 0; for (int i = 0; i <= n / 2; ++i) sum = ((lld)sum + (lld)dp.back()[i]) % (lld)INF; cout << sum << '\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 | #include <bits/stdc++.h> using namespace std; typedef long long lld; constexpr int INF = 1e9+7; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<vector<int> > dp(n, vector<int> (n / 2 + 1, 0)); dp[1][1] = m; for (int i = 2; i < n; ++i) for (int k = 1; k <= n / 2; ++k) dp[i][k] = ((lld)dp[i - 1][k] * (lld)m + (lld)dp[i - 2][k - 1] * (lld)(m - k + 1)) % (lld)INF; // 2*10^18 int sum = 0; for (int i = 0; i <= n / 2; ++i) sum = ((lld)sum + (lld)dp.back()[i]) % (lld)INF; cout << sum << '\n'; } |