#include<cstdio> int n, m, p; void input() { scanf("%d %d %d\n", &n, &m, &p); } int * t1s; int * t1e; bool inside(int x, int x2, int y2) { return x2 <= x && y2 >= x; } bool intersect(int x1, int y1, int x2, int y2) { return inside(x1, x2, y2) || inside(y1, x2, y2) || inside(x2, x1, y1) || inside(y2, x1, y1); } int brute1(int k) { if (k == n) { // printf("\n"); // for (int i = 0; i < m; i++) { // for (int j = 0; j < n; j++) { // if (t1s[j] <= i && t1e[j] >= i) { // printf("#"); // } else { // printf(" "); // } // } // printf("\n"); // } return 1; } int res = 0; for (int i = 0; i < m; i++) { for (int j = i; j < m; j++) { if (k == 0 || intersect(t1s[k - 1], t1e[k - 1], i, j)) { t1s[k] = i; t1e[k] = j; // printf("%d %d %d\n", k, i , j); res += brute1(k + 1); } } } // printf("%d %d\n", k, res); return res; } int brute1() { t1s = new int[n]; t1e = new int[n]; return brute1(0); } // x = i * m + j long long brute2() { int coef[m * m][m * m]; for (int i = 0; i < m * m; i++) { for (int j = 0; j < m * m; j++) { coef[i][j] = 0; } } int d[2][m * m]; for (int i1 = 0; i1 < m; i1++) { for (int j1 = i1; j1 < m; j1++) { for (int i2 = 0; i2 < m; i2++) { for (int j2 = i2; j2 < m; j2++) { if (intersect(i1, j1, i2, j2)) { coef[i2 * m + j2][i1 * m + j1] = 1; } else { coef[i2 * m + j2][i1 * m + j1] = 0; } } } } } // for (int i = 0; i < m * m; i++) { // for (int j = 0; j < m * m; j++) { // printf("%d ", coef[i][j]); // } // printf("\n"); // } for (int i = 0; i < m * m; i++) { d[0][i] = 1; } for (int i = 1; i < n; i++) { int k = i % 2; int l = 1 - k; for (int j = 0; j < m * m; j++) { d[k][j] = 0; d[l][j] %= p; } for (int i1 = 0; i1 < m; i1++) { for (int j1 = i1; j1 < m; j1++) { for (int i2 = 0; i2 < m; i2++) { for (int j2 = 0; j2 < m; j2++) { d[k][i1 * m + j1] += (coef[i1 * m + j1][i2 * m + j2] * (long long) d[l][i2 * m + j2]) % p; } } } } } long long res = 0; for (int i = 0; i < m * m; i++) { res = (res + d[(n + 1) % 2][i]) % p; } return res; } int main() { input(); // printf("%d\n", brute1() % p); printf("%lld\n", brute2() % p); 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 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 | #include<cstdio> int n, m, p; void input() { scanf("%d %d %d\n", &n, &m, &p); } int * t1s; int * t1e; bool inside(int x, int x2, int y2) { return x2 <= x && y2 >= x; } bool intersect(int x1, int y1, int x2, int y2) { return inside(x1, x2, y2) || inside(y1, x2, y2) || inside(x2, x1, y1) || inside(y2, x1, y1); } int brute1(int k) { if (k == n) { // printf("\n"); // for (int i = 0; i < m; i++) { // for (int j = 0; j < n; j++) { // if (t1s[j] <= i && t1e[j] >= i) { // printf("#"); // } else { // printf(" "); // } // } // printf("\n"); // } return 1; } int res = 0; for (int i = 0; i < m; i++) { for (int j = i; j < m; j++) { if (k == 0 || intersect(t1s[k - 1], t1e[k - 1], i, j)) { t1s[k] = i; t1e[k] = j; // printf("%d %d %d\n", k, i , j); res += brute1(k + 1); } } } // printf("%d %d\n", k, res); return res; } int brute1() { t1s = new int[n]; t1e = new int[n]; return brute1(0); } // x = i * m + j long long brute2() { int coef[m * m][m * m]; for (int i = 0; i < m * m; i++) { for (int j = 0; j < m * m; j++) { coef[i][j] = 0; } } int d[2][m * m]; for (int i1 = 0; i1 < m; i1++) { for (int j1 = i1; j1 < m; j1++) { for (int i2 = 0; i2 < m; i2++) { for (int j2 = i2; j2 < m; j2++) { if (intersect(i1, j1, i2, j2)) { coef[i2 * m + j2][i1 * m + j1] = 1; } else { coef[i2 * m + j2][i1 * m + j1] = 0; } } } } } // for (int i = 0; i < m * m; i++) { // for (int j = 0; j < m * m; j++) { // printf("%d ", coef[i][j]); // } // printf("\n"); // } for (int i = 0; i < m * m; i++) { d[0][i] = 1; } for (int i = 1; i < n; i++) { int k = i % 2; int l = 1 - k; for (int j = 0; j < m * m; j++) { d[k][j] = 0; d[l][j] %= p; } for (int i1 = 0; i1 < m; i1++) { for (int j1 = i1; j1 < m; j1++) { for (int i2 = 0; i2 < m; i2++) { for (int j2 = 0; j2 < m; j2++) { d[k][i1 * m + j1] += (coef[i1 * m + j1][i2 * m + j2] * (long long) d[l][i2 * m + j2]) % p; } } } } } long long res = 0; for (int i = 0; i < m * m; i++) { res = (res + d[(n + 1) % 2][i]) % p; } return res; } int main() { input(); // printf("%d\n", brute1() % p); printf("%lld\n", brute2() % p); return 0; } |