#include <iostream> using namespace std; const int MOD = 1e9+7; int maxn, m, w[3001][3001][2]; int f(int n, int ilek, int z) { if (w[n][ilek][z]) return w[n][ilek][z]; long long wynik = 0; if (n == 0) { if (z == 0) wynik = 1; goto end; } if (n == 1) { wynik = ilek; goto end; } if (z) wynik += f(n - 1, ilek, 0); if (ilek > z) wynik += (long long) f(n-1, ilek, 0) * (ilek - z) % MOD; if (ilek < m) { if (z) wynik += (long long) f(n - 1, ilek, 1) * (m - ilek) % MOD; else wynik += (long long) f(n - 1, ilek + 1, 1) * (m - ilek) % MOD; } end: wynik %= MOD; w[n][ilek][z] = wynik; return wynik; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> maxn >> m; cout << f(maxn, 0, 0) << endl; }
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 | #include <iostream> using namespace std; const int MOD = 1e9+7; int maxn, m, w[3001][3001][2]; int f(int n, int ilek, int z) { if (w[n][ilek][z]) return w[n][ilek][z]; long long wynik = 0; if (n == 0) { if (z == 0) wynik = 1; goto end; } if (n == 1) { wynik = ilek; goto end; } if (z) wynik += f(n - 1, ilek, 0); if (ilek > z) wynik += (long long) f(n-1, ilek, 0) * (ilek - z) % MOD; if (ilek < m) { if (z) wynik += (long long) f(n - 1, ilek, 1) * (m - ilek) % MOD; else wynik += (long long) f(n - 1, ilek + 1, 1) * (m - ilek) % MOD; } end: wynik %= MOD; w[n][ilek][z] = wynik; return wynik; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> maxn >> m; cout << f(maxn, 0, 0) << endl; } |