#include <cstdio> #include <cmath> #include <algorithm> const int _N = 1000; const int _K = 11; typedef long long integer; integer D[1007][21]; integer Modlitwa(int k, integer mod) { k--; integer res = 1; for (int i = 0; i < k; i++) { res = (res * 2) % mod; } return res; } void JanPawelDrugi() { D[1][0] = 1; D[2][1] = 2; D[3][1] = 4; D[3][2] = 2; D[4][1] = 8; D[4][2] = 16; D[5][1] = 16; D[5][2] = 100; D[5][3] = 4; D[6][1] = 32; D[6][2] = 616; D[6][3] = 72; D[7][1] = 64; D[7][2] = 4024; D[7][3] = 952; D[8][1] = 128; D[8][2] = 28512; D[8][3] = 11680; D[9][1] = 256; D[9][2] = 219664; D[9][3] = 142800; D[9][4] = 160; D[10][1] = 512; D[10][2] = 1831712; D[10][3] = 1788896; D[10][4] = 7680; D[11][1] = 1024LL; D[11][2] = 16429152LL; D[11][3] = 23252832LL; D[11][4] = 233792LL; D[12][1] = 2048LL; D[12][2] = 157552000LL; D[12][3] = 315549312LL; D[12][4] = 5898240LL; D[13][1] = 4096LL; D[13][2] = 1606874944LL; D[13][3] = 4483860928LL; D[13][4] = 136280832LL; } void Solve(int n, int k, integer mod) { int mK = log2(n - 1) + 1; if (k > 19) { printf("0\n"); return; } if (n <= 13) { printf("%lld\n", D[n][k] % mod); return; } if (k == 1) { printf("%lld\n", Modlitwa(n, mod) % mod); return; } printf("2137\n"); } int main() { JanPawelDrugi(); int n, k; integer mod; scanf("%d%d%lld", &n, &k, &mod); Solve(n, k, mod); 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 | #include <cstdio> #include <cmath> #include <algorithm> const int _N = 1000; const int _K = 11; typedef long long integer; integer D[1007][21]; integer Modlitwa(int k, integer mod) { k--; integer res = 1; for (int i = 0; i < k; i++) { res = (res * 2) % mod; } return res; } void JanPawelDrugi() { D[1][0] = 1; D[2][1] = 2; D[3][1] = 4; D[3][2] = 2; D[4][1] = 8; D[4][2] = 16; D[5][1] = 16; D[5][2] = 100; D[5][3] = 4; D[6][1] = 32; D[6][2] = 616; D[6][3] = 72; D[7][1] = 64; D[7][2] = 4024; D[7][3] = 952; D[8][1] = 128; D[8][2] = 28512; D[8][3] = 11680; D[9][1] = 256; D[9][2] = 219664; D[9][3] = 142800; D[9][4] = 160; D[10][1] = 512; D[10][2] = 1831712; D[10][3] = 1788896; D[10][4] = 7680; D[11][1] = 1024LL; D[11][2] = 16429152LL; D[11][3] = 23252832LL; D[11][4] = 233792LL; D[12][1] = 2048LL; D[12][2] = 157552000LL; D[12][3] = 315549312LL; D[12][4] = 5898240LL; D[13][1] = 4096LL; D[13][2] = 1606874944LL; D[13][3] = 4483860928LL; D[13][4] = 136280832LL; } void Solve(int n, int k, integer mod) { int mK = log2(n - 1) + 1; if (k > 19) { printf("0\n"); return; } if (n <= 13) { printf("%lld\n", D[n][k] % mod); return; } if (k == 1) { printf("%lld\n", Modlitwa(n, mod) % mod); return; } printf("2137\n"); } int main() { JanPawelDrugi(); int n, k; integer mod; scanf("%d%d%lld", &n, &k, &mod); Solve(n, k, mod); return 0; } |