#include <iostream> using namespace std; int N,K,P; long long snk[1001][1001]; long long SOL[12][21] = {{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {4, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {8, 16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {16, 100, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {32, 616, 72, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {64, 4024, 952, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {128, 28512, 11680, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {256, 219664, 142800, 160, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {512, 1831712, 1788896, 7680, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {1024, 16429152, 23252832, 233792, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {2048, 157552000, 315549312, 5898240, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}}; int maxValidNumber(int n) { int c = 0; while(n > 0) { n = n>>1; ++c; } return c; } long long firstCol() { long long W = 1; if (N == 1) return 1; int x = 0; while(x<N-1) { W = (W * 2) % P; ++x; } return W; } long long S(long long n,long long k) { if (k>n || k<0) return 0; if (n==0 and k==0 ) return 1; if (snk[n][k] == -1) { long long val = (S(n-1,k-1)) + ((2*(k+1)-1) * S(n-1,k)) % 2000000000; snk[n][k] = val % 2000000000; return snk[n][k]; } else { return snk[n][k] % 2000000000; } } long long DWN(int n) { long long sum = 1; for (int k=0;k<n;++k) { sum = (sum + S(n,k)) % 2000000000; sum = sum ; } return sum; } long long SecondCol() { //clear snk for (int x=0;x<1000;++x) for (int y=0;y<1000;++y) snk[x][y] = -1; /// return (DWN(N-1) - firstCol())%P; } int main(int argc, const char * argv[]) { scanf("%d %d %d",&N,&K,&P); if (K > maxValidNumber(N)) { printf("0\n"); return 0; } if (K == 1) { printf("%lld\n",firstCol()); return 0; } else if (K == 2) { printf("%lld\n",SecondCol()); } else { printf("%lld\n",SOL[N-1][K-1]%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 | #include <iostream> using namespace std; int N,K,P; long long snk[1001][1001]; long long SOL[12][21] = {{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {4, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {8, 16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {16, 100, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {32, 616, 72, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {64, 4024, 952, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {128, 28512, 11680, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {256, 219664, 142800, 160, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {512, 1831712, 1788896, 7680, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {1024, 16429152, 23252832, 233792, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {2048, 157552000, 315549312, 5898240, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}}; int maxValidNumber(int n) { int c = 0; while(n > 0) { n = n>>1; ++c; } return c; } long long firstCol() { long long W = 1; if (N == 1) return 1; int x = 0; while(x<N-1) { W = (W * 2) % P; ++x; } return W; } long long S(long long n,long long k) { if (k>n || k<0) return 0; if (n==0 and k==0 ) return 1; if (snk[n][k] == -1) { long long val = (S(n-1,k-1)) + ((2*(k+1)-1) * S(n-1,k)) % 2000000000; snk[n][k] = val % 2000000000; return snk[n][k]; } else { return snk[n][k] % 2000000000; } } long long DWN(int n) { long long sum = 1; for (int k=0;k<n;++k) { sum = (sum + S(n,k)) % 2000000000; sum = sum ; } return sum; } long long SecondCol() { //clear snk for (int x=0;x<1000;++x) for (int y=0;y<1000;++y) snk[x][y] = -1; /// return (DWN(N-1) - firstCol())%P; } int main(int argc, const char * argv[]) { scanf("%d %d %d",&N,&K,&P); if (K > maxValidNumber(N)) { printf("0\n"); return 0; } if (K == 1) { printf("%lld\n",firstCol()); return 0; } else if (K == 2) { printf("%lld\n",SecondCol()); } else { printf("%lld\n",SOL[N-1][K-1]%P); } return 0; } |