#include <stdio.h> long long t[250001][101], sum, d, i=1, j=0, lim[250001], n, k, m, val[530008], nn, c, wynn[250001]; void cal (long long n){ long long d=(n*(n-1))/2, c=0, z=m; if (m>d/2) z=d-m; if (z<0) c=-z, z=0; while (z<lim[n]&&t[n][z]<k){ k-=t[n][z]; z++, c++; } m-=c; wynn[i]=c; } void maledicti (long long a){ long long i=1; while (i<262144){ if (val[i*2]>a) i*=2; else i=i*2+1, a-=val[i-1]; val[i]--; } val[i]--; printf ("%d", i-262143); } int main(){ scanf ("%lld %lld", &n, &k); t[0][0]=1, lim[0]=1000; while (i<=n){ d=i*(i-1)/2; while (j<=d&&j<lim[i-1]&&j<101){ sum+=t[i-1][j]; if (j>=i) sum-=t[i-1][j-i]; t[i][j]=sum; if (t[i][j]>1000000000000000000LL) { t[i][j]=0, lim[i]=j; break; } j++; } if (lim[i]==0&&lim[i-1]==0) lim[i]=1000; else if (lim[i]==0) lim[i]=lim[i-1]; sum=0; j=0, i++; } i=0; if (n*(n-1)%4!=0) printf ("NIE"); else if (lim[n]==1000&&t[n][n*(n-1)/4]<k) printf ("NIE"); else { printf ("TAK\n"); nn=n, m=(n*(n-1))/4, n--; while (n>0){ cal (n); i++, n--; } } i=530001; while (i>=262144){ val[i]=1; i--; } while (i>0){ val[i]=val[i*2]+val[i*2+1]; i--; } i=0; while (i<nn){ maledicti (wynn[i]); i++; if (i!=nn) printf (" "); } 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 | #include <stdio.h> long long t[250001][101], sum, d, i=1, j=0, lim[250001], n, k, m, val[530008], nn, c, wynn[250001]; void cal (long long n){ long long d=(n*(n-1))/2, c=0, z=m; if (m>d/2) z=d-m; if (z<0) c=-z, z=0; while (z<lim[n]&&t[n][z]<k){ k-=t[n][z]; z++, c++; } m-=c; wynn[i]=c; } void maledicti (long long a){ long long i=1; while (i<262144){ if (val[i*2]>a) i*=2; else i=i*2+1, a-=val[i-1]; val[i]--; } val[i]--; printf ("%d", i-262143); } int main(){ scanf ("%lld %lld", &n, &k); t[0][0]=1, lim[0]=1000; while (i<=n){ d=i*(i-1)/2; while (j<=d&&j<lim[i-1]&&j<101){ sum+=t[i-1][j]; if (j>=i) sum-=t[i-1][j-i]; t[i][j]=sum; if (t[i][j]>1000000000000000000LL) { t[i][j]=0, lim[i]=j; break; } j++; } if (lim[i]==0&&lim[i-1]==0) lim[i]=1000; else if (lim[i]==0) lim[i]=lim[i-1]; sum=0; j=0, i++; } i=0; if (n*(n-1)%4!=0) printf ("NIE"); else if (lim[n]==1000&&t[n][n*(n-1)/4]<k) printf ("NIE"); else { printf ("TAK\n"); nn=n, m=(n*(n-1))/4, n--; while (n>0){ cal (n); i++, n--; } } i=530001; while (i>=262144){ val[i]=1; i--; } while (i>0){ val[i]=val[i*2]+val[i*2+1]; i--; } i=0; while (i<nn){ maledicti (wynn[i]); i++; if (i!=nn) printf (" "); } return 0;} |