#include <bits/stdc++.h> #define ll long long #define debug if(0) const int MAX_N = 3000; int n; ll m; const ll MOD = 1e9+7; ll good[MAX_N+3][MAX_N+3]; ll bad[MAX_N+3][MAX_N+3]; int main() { std::ios_base::sync_with_stdio(0); std::cin.tie(NULL); std::cin >> n >> m; int diff = std::max(m-n, (ll)(0)); /* baza dla n = 1 */ bad[1][m-1 - diff] = m; for (int i = 2; i <= n; i++) { for (ll k = diff; k <= m; k++) { good[i][k - diff] = ((good[i-1][k - diff] + bad[i-1][k - diff]) * (m-k)) % MOD; bad[i][k - diff] = bad[i-1][k - diff] * k % MOD; if (k+1 <= m) bad[i][k - diff] = (bad[i][k - diff] + ((good[i-1][k + 1 - diff] * (k+1) % MOD)) % MOD); debug { std::cout << "good[" << i << "][" << k << "] = " << good[i][k-diff] << "\n"; std::cout << "bad[" << i << "][" << k << "] = " << bad[i][k-diff] << "\n"; } } } ll res = 0; for (int k = diff; k <= m; k++) res = (res + good[n][k - diff]) % MOD; std::cout << res << "\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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | #include <bits/stdc++.h> #define ll long long #define debug if(0) const int MAX_N = 3000; int n; ll m; const ll MOD = 1e9+7; ll good[MAX_N+3][MAX_N+3]; ll bad[MAX_N+3][MAX_N+3]; int main() { std::ios_base::sync_with_stdio(0); std::cin.tie(NULL); std::cin >> n >> m; int diff = std::max(m-n, (ll)(0)); /* baza dla n = 1 */ bad[1][m-1 - diff] = m; for (int i = 2; i <= n; i++) { for (ll k = diff; k <= m; k++) { good[i][k - diff] = ((good[i-1][k - diff] + bad[i-1][k - diff]) * (m-k)) % MOD; bad[i][k - diff] = bad[i-1][k - diff] * k % MOD; if (k+1 <= m) bad[i][k - diff] = (bad[i][k - diff] + ((good[i-1][k + 1 - diff] * (k+1) % MOD)) % MOD); debug { std::cout << "good[" << i << "][" << k << "] = " << good[i][k-diff] << "\n"; std::cout << "bad[" << i << "][" << k << "] = " << bad[i][k-diff] << "\n"; } } } ll res = 0; for (int k = diff; k <= m; k++) res = (res + good[n][k - diff]) % MOD; std::cout << res << "\n"; } |