#include <iostream> #include <cstdio> using namespace std; long long result[1005][15]; long long jeden[1005][15]; long long dwa[1005][15]; long long jeden_do[1005][15]; long long dwa_do[1005][15]; long long BiNom[1005][1005]; int potegi[15]; int n, k; long long p, teraz; int log_sufit (int N) { int potega = 1; int wynik = 0; while (potega < N) { potega *= 2; wynik++; } return wynik; } int main () { potegi[0] = 1; for (int i = 1; i < 15; ++i) potegi[i] = 2 * potegi[i - 1]; scanf("%d%d%lld", &n, &k, &p); if (k > log_sufit(n)) { printf("0\n"); return 0; } for (int i = 0; i <= 1000; ++i) BiNom[i][0] = 1; for (int j = 1; j <= 1000; ++j) for (int i = j; i <= 1000; ++i) BiNom[i][j] = (BiNom[i - 1][j - 1] + BiNom[i - 1][j]) % p; result[1][1]= 1; for (int i = 2; i <= n; ++i) result[i][1] = (result[i - 1][1] * 2) % p; for (int i = 1; i <= n; ++i) jeden_do[i][1] = jeden[i][1] = 1; dwa_do[2][1] = dwa[2][1] = 1; for (int j = 2; j <= k; ++j) { for (int i = 2; i <= potegi[j - 1]; ++i) { dwa_do[i][j] = dwa_do[i][j - 1]; jeden_do[i][j] = jeden_do[i][j - 1]; } for (int i = potegi[j - 1] + 1; i <= n; ++i) { for (int m = 2; m < i; ++m) { teraz = dwa[m][j - 1] * dwa[i - m + 1][j - 1] + dwa[m][j] * dwa_do[i - m + 1][j - 1] + dwa_do[m][j - 1] * dwa[i - m + 1][j]; teraz %= p; dwa[i][j] += BiNom[i - 3][m - 2] * teraz; dwa[i][j] %= p; } dwa_do[i][j] = (dwa_do[i][j - 1] + dwa[i][j]) % p; jeden[i][j] = dwa[i][j]; for (int m = 2; m < i; ++m) { teraz = jeden[m][j] * dwa_do[i - m + 1][j] + jeden_do[m][j - 1] * dwa[i - m + 1][j]; teraz %= p; jeden[i][j] += BiNom[i - 2][m - 1] * teraz; jeden[i][j] %= p; } jeden_do[i][j] = (jeden_do[i][j - 1] + jeden[i][j]) % p; result[i][j] = (2 * jeden[i][j]) % p; for (int m = 2; m < i; ++m) { teraz = jeden[m][j] * jeden_do[i - m + 1][j] + jeden_do[m][j - 1] * jeden[i - m + 1][j]; teraz %= p; result[i][j] += BiNom[i - 1][m - 1] * teraz; result[i][j] %= p; } } } printf("%lld\n", result[n][k]); 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 | #include <iostream> #include <cstdio> using namespace std; long long result[1005][15]; long long jeden[1005][15]; long long dwa[1005][15]; long long jeden_do[1005][15]; long long dwa_do[1005][15]; long long BiNom[1005][1005]; int potegi[15]; int n, k; long long p, teraz; int log_sufit (int N) { int potega = 1; int wynik = 0; while (potega < N) { potega *= 2; wynik++; } return wynik; } int main () { potegi[0] = 1; for (int i = 1; i < 15; ++i) potegi[i] = 2 * potegi[i - 1]; scanf("%d%d%lld", &n, &k, &p); if (k > log_sufit(n)) { printf("0\n"); return 0; } for (int i = 0; i <= 1000; ++i) BiNom[i][0] = 1; for (int j = 1; j <= 1000; ++j) for (int i = j; i <= 1000; ++i) BiNom[i][j] = (BiNom[i - 1][j - 1] + BiNom[i - 1][j]) % p; result[1][1]= 1; for (int i = 2; i <= n; ++i) result[i][1] = (result[i - 1][1] * 2) % p; for (int i = 1; i <= n; ++i) jeden_do[i][1] = jeden[i][1] = 1; dwa_do[2][1] = dwa[2][1] = 1; for (int j = 2; j <= k; ++j) { for (int i = 2; i <= potegi[j - 1]; ++i) { dwa_do[i][j] = dwa_do[i][j - 1]; jeden_do[i][j] = jeden_do[i][j - 1]; } for (int i = potegi[j - 1] + 1; i <= n; ++i) { for (int m = 2; m < i; ++m) { teraz = dwa[m][j - 1] * dwa[i - m + 1][j - 1] + dwa[m][j] * dwa_do[i - m + 1][j - 1] + dwa_do[m][j - 1] * dwa[i - m + 1][j]; teraz %= p; dwa[i][j] += BiNom[i - 3][m - 2] * teraz; dwa[i][j] %= p; } dwa_do[i][j] = (dwa_do[i][j - 1] + dwa[i][j]) % p; jeden[i][j] = dwa[i][j]; for (int m = 2; m < i; ++m) { teraz = jeden[m][j] * dwa_do[i - m + 1][j] + jeden_do[m][j - 1] * dwa[i - m + 1][j]; teraz %= p; jeden[i][j] += BiNom[i - 2][m - 1] * teraz; jeden[i][j] %= p; } jeden_do[i][j] = (jeden_do[i][j - 1] + jeden[i][j]) % p; result[i][j] = (2 * jeden[i][j]) % p; for (int m = 2; m < i; ++m) { teraz = jeden[m][j] * jeden_do[i - m + 1][j] + jeden_do[m][j - 1] * jeden[i - m + 1][j]; teraz %= p; result[i][j] += BiNom[i - 1][m - 1] * teraz; result[i][j] %= p; } } } printf("%lld\n", result[n][k]); return 0; } |