#include <iostream> using namespace std; const int mod = 1000000007; const int maxN = 3000; const int maxM = 1000000000; int result[maxN + 5][maxN + 5]; int gatunki; long long fun(int n, int a) { if(n < 0) return 0; if (n == 0) return 1 ; //max(gatunki - a, 0); if (n == 1) return 0; if (gatunki <= a) return 0; if (result[n][a] == 0) { // long long res = 0; // long long other = 1; // for (int i = 2; i <= n; i++) { // //// long long tym = fun(n - i, a + 1); //// cout<<"fun("<<n-i<<", "<<a + 1<<")="<<tym<<"\n"; // // res = (res + fun(n - i, a + 1) * other) % mod; // other = (other * (gatunki - a)) % mod; // } long long res = (fun(n-1, a) + fun(n-2, a+1)) % mod; res = (res * (gatunki - a)) % mod; result[n][a] = res; } return result[n][a]; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> gatunki; // long long tym = fun(n , 0); // cout<<"fun("<<n<<", "<<0<<")="<<tym<<"\n"; //cout<<"wrong."<<"\n"; cout << fun(n , 0) << "\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 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 | #include <iostream> using namespace std; const int mod = 1000000007; const int maxN = 3000; const int maxM = 1000000000; int result[maxN + 5][maxN + 5]; int gatunki; long long fun(int n, int a) { if(n < 0) return 0; if (n == 0) return 1 ; //max(gatunki - a, 0); if (n == 1) return 0; if (gatunki <= a) return 0; if (result[n][a] == 0) { // long long res = 0; // long long other = 1; // for (int i = 2; i <= n; i++) { // //// long long tym = fun(n - i, a + 1); //// cout<<"fun("<<n-i<<", "<<a + 1<<")="<<tym<<"\n"; // // res = (res + fun(n - i, a + 1) * other) % mod; // other = (other * (gatunki - a)) % mod; // } long long res = (fun(n-1, a) + fun(n-2, a+1)) % mod; res = (res * (gatunki - a)) % mod; result[n][a] = res; } return result[n][a]; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> gatunki; // long long tym = fun(n , 0); // cout<<"fun("<<n<<", "<<0<<")="<<tym<<"\n"; //cout<<"wrong."<<"\n"; cout << fun(n , 0) << "\n"; } |