#include <bits/stdc++.h> #define ll long long using namespace std; const ll INF = (1ll<<60); ll fast_pow(int a, int k) { if (k == 0) return 1; return fast_pow((a*a), k/2) * ((k % 2 == 0) ? 1 : a); } void __exit(ll ans) { cout << ans <<endl; exit(0); } int get_ans(int n, int P[]) { if (n == 1) return 0; vector <int> V, W; for (int i = 0; i < n; i++) if ((i-1 < 0 || P[i-1] < P[i]) && (i+1 >= n || P[i+1] < P[i])) V.push_back(P[i]); int ans = 1; while (V.size() > 1) { ans++; n = V.size(); for (int i = 0; i < n; i++) if ((i-1 < 0 || V[i-1] < V[i]) && (i+1 >= n || V[i+1] < V[i])) W.push_back(V[i]); V = W; W.clear(); } return ans; } void solve_for_n_to_10(ll n, ll k, ll q) { int P[n]; for (int i = 0; i < n; i++) P[i] = i; ll ans = 0; do { if (get_ans(n, P) == k) ans++; } while (next_permutation(&P[0], &P[n])); __exit(ans % q); } void solve_for_greater_n(ll n, ll k, ll q) { ll Sil[n+1]; Sil[0] = Sil[1] = 1; for (int i = 2; i <= n; i++) Sil[i] = (Sil[i-1] * i) % q; vector < vector <ll> > D(n+1, vector <ll> (k+1, 0)), O(n+1, vector <ll> (n+1, 0)); /* O[i][j] - na ile sposobów można obudować i elementami j większych elementów */ D[1][0] = 1; //D[2][1] = 2; //O[0][0] = 1; O[0][1] = 1; O[1][1] = 2; O[1][2] = 1; /*O[2][1] = 4; O[2][2] = 2+2*2; O[2][3] = 2;*/ for (int i = 2; i <= n; i++) { for (int j = 1; j <= k; j++) { for (int l = 1; l < i; l++) { if (j > 1) D[i][j] += D[i-l][j] * O[l][1]; D[i][j] = (D[i][j] + D[l][j-1] * ((O[i-l][l]) % q)) % q; //cout << i << " " << j << " " << l << " | " << D[l][j-1] << " " << O[i-l][l] <<endl; } } //O[i][1] = (O[i-1][1] * 2) % q; for (int l = 1; l <= i; l++) { O[i][l] = (O[i-1][l] * (2*l) + O[i-1][l-1] * (l-1)) % q; //cout << i << " " << l << " " << O[i][l] <<endl; } O[i][i+1] = Sil[i]; } __exit(D[n][k]); } int main() { ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); ll n, k, q; cin >> n >> k >> q; if (k > 30 || fast_pow(2, k) > 2 * n) __exit(0); if (n <= 11) { solve_for_n_to_10(n, k, q); } else { solve_for_greater_n(n, k, q); } 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 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 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 | #include <bits/stdc++.h> #define ll long long using namespace std; const ll INF = (1ll<<60); ll fast_pow(int a, int k) { if (k == 0) return 1; return fast_pow((a*a), k/2) * ((k % 2 == 0) ? 1 : a); } void __exit(ll ans) { cout << ans <<endl; exit(0); } int get_ans(int n, int P[]) { if (n == 1) return 0; vector <int> V, W; for (int i = 0; i < n; i++) if ((i-1 < 0 || P[i-1] < P[i]) && (i+1 >= n || P[i+1] < P[i])) V.push_back(P[i]); int ans = 1; while (V.size() > 1) { ans++; n = V.size(); for (int i = 0; i < n; i++) if ((i-1 < 0 || V[i-1] < V[i]) && (i+1 >= n || V[i+1] < V[i])) W.push_back(V[i]); V = W; W.clear(); } return ans; } void solve_for_n_to_10(ll n, ll k, ll q) { int P[n]; for (int i = 0; i < n; i++) P[i] = i; ll ans = 0; do { if (get_ans(n, P) == k) ans++; } while (next_permutation(&P[0], &P[n])); __exit(ans % q); } void solve_for_greater_n(ll n, ll k, ll q) { ll Sil[n+1]; Sil[0] = Sil[1] = 1; for (int i = 2; i <= n; i++) Sil[i] = (Sil[i-1] * i) % q; vector < vector <ll> > D(n+1, vector <ll> (k+1, 0)), O(n+1, vector <ll> (n+1, 0)); /* O[i][j] - na ile sposobów można obudować i elementami j większych elementów */ D[1][0] = 1; //D[2][1] = 2; //O[0][0] = 1; O[0][1] = 1; O[1][1] = 2; O[1][2] = 1; /*O[2][1] = 4; O[2][2] = 2+2*2; O[2][3] = 2;*/ for (int i = 2; i <= n; i++) { for (int j = 1; j <= k; j++) { for (int l = 1; l < i; l++) { if (j > 1) D[i][j] += D[i-l][j] * O[l][1]; D[i][j] = (D[i][j] + D[l][j-1] * ((O[i-l][l]) % q)) % q; //cout << i << " " << j << " " << l << " | " << D[l][j-1] << " " << O[i-l][l] <<endl; } } //O[i][1] = (O[i-1][1] * 2) % q; for (int l = 1; l <= i; l++) { O[i][l] = (O[i-1][l] * (2*l) + O[i-1][l-1] * (l-1)) % q; //cout << i << " " << l << " " << O[i][l] <<endl; } O[i][i+1] = Sil[i]; } __exit(D[n][k]); } int main() { ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); ll n, k, q; cin >> n >> k >> q; if (k > 30 || fast_pow(2, k) > 2 * n) __exit(0); if (n <= 11) { solve_for_n_to_10(n, k, q); } else { solve_for_greater_n(n, k, q); } return 0; } |