#include <cstdio> using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) #define INT(x) int x; scanf("%d", &x) typedef long long LL; int binom[1000][1000]; int res[1001][11][3]; int main() { INT(n); INT(k); INT(p); int d = 0, nn = n; while (nn > 1) { ++nn >>= 1; ++d; } if (k > d) { printf("0\n"); return 0; } binom[0][0] = 1; FOR(i,1,n) REP(j,i+1) { if (j) binom[i][j] = binom[i - 1][j - 1]; if (j < i) binom[i][j] = (binom[i][j] + binom[i - 1][j]) % p; } REP(j,k+1) REP(a,3) res[0][j][a] = 1; REP(i,n+1) REP(j,k+1) { REP(x,i) res[i][j][0] = (res[i][j][0] + LL(res[x][j][1]) * res[i - x - 1][j][1] % p * binom[i - 1][x] % p) % p; if (j) { REP(x,i) res[i][j][1] = (res[i][j][1] + LL(res[x][j][1]) * res[i - x - 1][j - 1][2] % p * binom[i - 1][x] % p) % p; REP(x,i) res[i][j][2] = (res[i][j][2] + ((LL(res[x][j][2]) * res[i - x - 1][j - 1][2] % p + LL(res[x][j - 1][2]) * res[i - x - 1][j][2] % p) % p + (p - LL(res[x][j - 1][2]) * res[i - x - 1][j - 1][2] % p) % p) % p * binom[i - 1][x] % p) % p; } } printf("%d\n", (res[n][k][0] + (p - res[n][k - 1][0]) % p) % p); }
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 | #include <cstdio> using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) #define INT(x) int x; scanf("%d", &x) typedef long long LL; int binom[1000][1000]; int res[1001][11][3]; int main() { INT(n); INT(k); INT(p); int d = 0, nn = n; while (nn > 1) { ++nn >>= 1; ++d; } if (k > d) { printf("0\n"); return 0; } binom[0][0] = 1; FOR(i,1,n) REP(j,i+1) { if (j) binom[i][j] = binom[i - 1][j - 1]; if (j < i) binom[i][j] = (binom[i][j] + binom[i - 1][j]) % p; } REP(j,k+1) REP(a,3) res[0][j][a] = 1; REP(i,n+1) REP(j,k+1) { REP(x,i) res[i][j][0] = (res[i][j][0] + LL(res[x][j][1]) * res[i - x - 1][j][1] % p * binom[i - 1][x] % p) % p; if (j) { REP(x,i) res[i][j][1] = (res[i][j][1] + LL(res[x][j][1]) * res[i - x - 1][j - 1][2] % p * binom[i - 1][x] % p) % p; REP(x,i) res[i][j][2] = (res[i][j][2] + ((LL(res[x][j][2]) * res[i - x - 1][j - 1][2] % p + LL(res[x][j - 1][2]) * res[i - x - 1][j][2] % p) % p + (p - LL(res[x][j - 1][2]) * res[i - x - 1][j - 1][2] % p) % p) % p * binom[i - 1][x] % p) % p; } } printf("%d\n", (res[n][k][0] + (p - res[n][k - 1][0]) % p) % p); } |