#include <cstdio> #include <algorithm> #include <vector> #include <set> const int M = 1000; const long long Q = ((long long)(1e18)) + 1; const int N = 250100; const int INV = 8; long long dp[M][M]; long long dp2[N][INV]; void init() { dp[0][0] = dp[1][0] = 1; for (int n = 2; n < M; n++) { for (int inv = 0; inv < M && inv <= n*(n-1)/2; inv++) { for(int x = 1; x <= n && x-1 <= inv; x++) { dp[n][inv] += dp[n-1][inv - x + 1]; if(dp[n][inv] >= Q) { dp[n][inv] = Q; break; } } // if(dp[n][inv] < Q )printf("%lld ", dp[n][inv]); } // printf("\n"); } for(int inv = 0; inv < INV; inv++) dp2[M-1][inv] = dp[M-1][inv]; for(int n = M; n < N; n++) { dp2[n][0] = 1; for(int inv = 1; inv < INV; inv++) { dp2[n][inv] = std::min(Q, dp2[n][inv-1] + dp2[n-1][inv]); // if(dp2[n][inv] < Q)printf("%lld ", dp2[n][inv]); } // printf("\n"); } } long long ub(int n) { return ((long long)n) * (n-1) / 2; } long long get(int n, long long inv) { long long w = ub(n); if (inv > w || inv < 0) return 0; if (inv > w-inv) inv = w-inv; if (inv == 0) return 1; if (n < M) { if (inv < M) return dp[n][inv]; else return Q; } if (inv < INV) return dp2[n][inv]; return Q; } const int U = 1<<18; int e[U+U]; void zb_init(int n) { for(int i = 1; i <= n; i++) e[U+i] = 1; for(int i = U-1; i > 0; i--) e[i] = e[i+i] + e[i+i+1]; } int zb_find(int x) { int i; for (i = 1; i < U; ) { e[i]--; if (e[i+i] >= x) i=i+i; else { x -= e[i+i]; i = i+i+1; } } e[i]--; return i - U; } std::vector<int> go(int n, long long k) { long long inv = ub(n); if (inv % 2) return std::vector<int>(); inv /= 2; if (get(n, inv) < k) return std::vector<int>(); std::vector<int> ret; zb_init(n); for (int i = 0; i < n; i++) { long long r = ub(n-i-1); for (long long x = std::max(inv - r, 0LL) + 1; x <= n-i; x++) { long long q = get(n-i-1, inv - x + 1); //printf("(%lld %lld -- %d %d %lld) ",q, k, n-i, x, inv); if (q >= k) { // printf("%d ", x); ret.push_back(zb_find(x)); inv -= x-1; break; } else { k -= q; } } } // printf("\n"); return ret; } int main() { init(); int n; long long k; scanf("%d %lld",&n,&k); std::vector<int> x = go(n, k); if (x.empty()) { printf("NIE\n"); } else { printf("TAK\n"); for(int i = 0; i < n; i++) printf("%d ", x[i]); printf("\n"); } 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 117 118 119 120 121 122 123 124 125 | #include <cstdio> #include <algorithm> #include <vector> #include <set> const int M = 1000; const long long Q = ((long long)(1e18)) + 1; const int N = 250100; const int INV = 8; long long dp[M][M]; long long dp2[N][INV]; void init() { dp[0][0] = dp[1][0] = 1; for (int n = 2; n < M; n++) { for (int inv = 0; inv < M && inv <= n*(n-1)/2; inv++) { for(int x = 1; x <= n && x-1 <= inv; x++) { dp[n][inv] += dp[n-1][inv - x + 1]; if(dp[n][inv] >= Q) { dp[n][inv] = Q; break; } } // if(dp[n][inv] < Q )printf("%lld ", dp[n][inv]); } // printf("\n"); } for(int inv = 0; inv < INV; inv++) dp2[M-1][inv] = dp[M-1][inv]; for(int n = M; n < N; n++) { dp2[n][0] = 1; for(int inv = 1; inv < INV; inv++) { dp2[n][inv] = std::min(Q, dp2[n][inv-1] + dp2[n-1][inv]); // if(dp2[n][inv] < Q)printf("%lld ", dp2[n][inv]); } // printf("\n"); } } long long ub(int n) { return ((long long)n) * (n-1) / 2; } long long get(int n, long long inv) { long long w = ub(n); if (inv > w || inv < 0) return 0; if (inv > w-inv) inv = w-inv; if (inv == 0) return 1; if (n < M) { if (inv < M) return dp[n][inv]; else return Q; } if (inv < INV) return dp2[n][inv]; return Q; } const int U = 1<<18; int e[U+U]; void zb_init(int n) { for(int i = 1; i <= n; i++) e[U+i] = 1; for(int i = U-1; i > 0; i--) e[i] = e[i+i] + e[i+i+1]; } int zb_find(int x) { int i; for (i = 1; i < U; ) { e[i]--; if (e[i+i] >= x) i=i+i; else { x -= e[i+i]; i = i+i+1; } } e[i]--; return i - U; } std::vector<int> go(int n, long long k) { long long inv = ub(n); if (inv % 2) return std::vector<int>(); inv /= 2; if (get(n, inv) < k) return std::vector<int>(); std::vector<int> ret; zb_init(n); for (int i = 0; i < n; i++) { long long r = ub(n-i-1); for (long long x = std::max(inv - r, 0LL) + 1; x <= n-i; x++) { long long q = get(n-i-1, inv - x + 1); //printf("(%lld %lld -- %d %d %lld) ",q, k, n-i, x, inv); if (q >= k) { // printf("%d ", x); ret.push_back(zb_find(x)); inv -= x-1; break; } else { k -= q; } } } // printf("\n"); return ret; } int main() { init(); int n; long long k; scanf("%d %lld",&n,&k); std::vector<int> x = go(n, k); if (x.empty()) { printf("NIE\n"); } else { printf("TAK\n"); for(int i = 0; i < n; i++) printf("%d ", x[i]); printf("\n"); } return 0; } |