#include <bits/stdc++.h> #define rep(i, a, b) for (int i = a; i <= b; i++) #define per(i, a, b) for (int i = b; a <= i; i--) #define cat(x) cerr << #x << " = " << x << '\n'; using ll = long long; using namespace std; const int N = 3030; const int P = 1e9 + 7; void add(int &a, int b) { a += b; if (a >= P) a -= P; } int n, m, dp[N][N][2]; int main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> m; dp[1][1][0] = m; rep(i, 1, n - 1) { rep(j, 1, i) { add(dp[i + 1][j][1], 1ll * j * (dp[i][j][0] + dp[i][j][1]) % P); add(dp[i + 1][j][0], 1ll * (m - j) * dp[i][j][0] % P); add(dp[i + 1][j + 1][0], 1ll * (m - j) * dp[i][j][1] % P); } } int res = 0; rep(i, 1, n) add(res, dp[n][i][1]); cout << res << '\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 | #include <bits/stdc++.h> #define rep(i, a, b) for (int i = a; i <= b; i++) #define per(i, a, b) for (int i = b; a <= i; i--) #define cat(x) cerr << #x << " = " << x << '\n'; using ll = long long; using namespace std; const int N = 3030; const int P = 1e9 + 7; void add(int &a, int b) { a += b; if (a >= P) a -= P; } int n, m, dp[N][N][2]; int main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> m; dp[1][1][0] = m; rep(i, 1, n - 1) { rep(j, 1, i) { add(dp[i + 1][j][1], 1ll * j * (dp[i][j][0] + dp[i][j][1]) % P); add(dp[i + 1][j][0], 1ll * (m - j) * dp[i][j][0] % P); add(dp[i + 1][j + 1][0], 1ll * (m - j) * dp[i][j][1] % P); } } int res = 0; rep(i, 1, n) add(res, dp[n][i][1]); cout << res << '\n'; return 0; } |