#include <iostream> #include <cstdint> #include <cstdio> #define PRINT(ARG) std::cout << #ARG << " = " << ARG << std::endl; typedef int32_t int32; typedef int64_t int64; typedef uint64_t uint64; struct Letter{ int32 occurences=0,first=-1, last=-1; int64 csR, csL; }; Letter l[26]; uint64 hash(unsigned char * str, int32 len, bool rev=false); static inline bool is_even(int32 v) {return !(v&1);} uint64 gcd(uint64 a, uint64 b); uint64 factorize(int64 number); uint64 n; const char NEWLINE = '\n'; const char SPACE = ' '; const int32 MAX_H = 16384; const int32 MAX_B = 312500; int64 hashList[MAX_H]; unsigned char charBuffer[MAX_B]; int32 bufferCount = 1; int32 bufferSize = 1; int32 padding = 0; bool even = false; bool is_palindrome = true; int main(){ std::ios_base::sync_with_stdio(0); std::cin >> n; if(n==0){ char c; int32 iter = 0; std::cin.getline(nullptr, 0); while(std::cin.get(c) && c != NEWLINE){ int32 i=c-97; l[i].last = iter; if(l[i].occurences == 0){ l[i].first = iter; } l[i].csL += iter; for(int32 i=0; i<26; i++){l[i].csR += l[i].occurences;} l[i].occurences++; iter++; } for(int32 i=0; i<26; i++){ if(l[i].csR != l[i].csL){ is_palindrome = false; break; } if(is_even(iter)){ if(!is_even(l[i].occurences)){ is_palindrome = false; break; } } if(l[i].occurences != 0 && l[i].first+1 != iter - l[i].last){ is_palindrome = false; break; } } }else{ if(is_even(n)){ even=true; n/=2; } int32 div = 0, tempBufferCount = 0, tempN = n; while(tempN != 1){ div = factorize(tempN); tempN = tempN/div; tempBufferCount = bufferCount; bufferCount *= div; if(bufferCount > MAX_H){ //TODO primes bufferCount = tempBufferCount; break; } } bufferSize = n/bufferCount; std::cin.getline(nullptr, 0); char c; int32 iter = 0, iter2 = 0; while(std::cin.get(c) && iter2 < bufferCount *2){ for(int32 j=0; j<(even?1:2); j++){ if(iter2+j < bufferCount){ charBuffer[iter] = c; iter++; if(iter%bufferSize == 0){ int64 h; hashList[iter2] = h = hash(charBuffer, bufferSize); iter2++; iter = 0; } }else{ charBuffer[iter] = c; iter++; if(iter%bufferSize == 0){ int64 h = hash(charBuffer, bufferSize, true); if( h != hashList[2*bufferCount - iter2-1]){ is_palindrome = false; //break; } iter2++; iter = 0; } } } } } std::cout << (is_palindrome ? "TAK" : "NIE"); } uint64 hash ( unsigned char * str, int32 len, bool rev) { uint64 h = 0, p = 1000000007, k = 33; if(rev){ for ( int32 i = 0; i < len; i++ ){ h = (h*k + str[i])%p; } } else{ for ( int32 i = len-1; i >= 0; i-- ){ h = (h*k + str[i])%p; } } return h; } uint64 gcd(uint64 a, uint64 b) { uint64 remainder; while (b != 0) { remainder = a % b; a = b; b = remainder; } return a; } uint64 factorize(int64 number){ int64 count, loop = 1; int64 x_fixed = 2, size = 2, x = 2, factor = 1; while (factor == 1) { for (count = 1; (count <= size) && (factor <= 1); count++) { x = (x * x + 1) % number; factor = gcd(abs(x - x_fixed), number); } size = 2 * size; x_fixed = x; loop = loop + 1; } return factor; }
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 126 127 128 129 130 131 132 133 134 135 136 137 138 139 | #include <iostream> #include <cstdint> #include <cstdio> #define PRINT(ARG) std::cout << #ARG << " = " << ARG << std::endl; typedef int32_t int32; typedef int64_t int64; typedef uint64_t uint64; struct Letter{ int32 occurences=0,first=-1, last=-1; int64 csR, csL; }; Letter l[26]; uint64 hash(unsigned char * str, int32 len, bool rev=false); static inline bool is_even(int32 v) {return !(v&1);} uint64 gcd(uint64 a, uint64 b); uint64 factorize(int64 number); uint64 n; const char NEWLINE = '\n'; const char SPACE = ' '; const int32 MAX_H = 16384; const int32 MAX_B = 312500; int64 hashList[MAX_H]; unsigned char charBuffer[MAX_B]; int32 bufferCount = 1; int32 bufferSize = 1; int32 padding = 0; bool even = false; bool is_palindrome = true; int main(){ std::ios_base::sync_with_stdio(0); std::cin >> n; if(n==0){ char c; int32 iter = 0; std::cin.getline(nullptr, 0); while(std::cin.get(c) && c != NEWLINE){ int32 i=c-97; l[i].last = iter; if(l[i].occurences == 0){ l[i].first = iter; } l[i].csL += iter; for(int32 i=0; i<26; i++){l[i].csR += l[i].occurences;} l[i].occurences++; iter++; } for(int32 i=0; i<26; i++){ if(l[i].csR != l[i].csL){ is_palindrome = false; break; } if(is_even(iter)){ if(!is_even(l[i].occurences)){ is_palindrome = false; break; } } if(l[i].occurences != 0 && l[i].first+1 != iter - l[i].last){ is_palindrome = false; break; } } }else{ if(is_even(n)){ even=true; n/=2; } int32 div = 0, tempBufferCount = 0, tempN = n; while(tempN != 1){ div = factorize(tempN); tempN = tempN/div; tempBufferCount = bufferCount; bufferCount *= div; if(bufferCount > MAX_H){ //TODO primes bufferCount = tempBufferCount; break; } } bufferSize = n/bufferCount; std::cin.getline(nullptr, 0); char c; int32 iter = 0, iter2 = 0; while(std::cin.get(c) && iter2 < bufferCount *2){ for(int32 j=0; j<(even?1:2); j++){ if(iter2+j < bufferCount){ charBuffer[iter] = c; iter++; if(iter%bufferSize == 0){ int64 h; hashList[iter2] = h = hash(charBuffer, bufferSize); iter2++; iter = 0; } }else{ charBuffer[iter] = c; iter++; if(iter%bufferSize == 0){ int64 h = hash(charBuffer, bufferSize, true); if( h != hashList[2*bufferCount - iter2-1]){ is_palindrome = false; //break; } iter2++; iter = 0; } } } } } std::cout << (is_palindrome ? "TAK" : "NIE"); } uint64 hash ( unsigned char * str, int32 len, bool rev) { uint64 h = 0, p = 1000000007, k = 33; if(rev){ for ( int32 i = 0; i < len; i++ ){ h = (h*k + str[i])%p; } } else{ for ( int32 i = len-1; i >= 0; i-- ){ h = (h*k + str[i])%p; } } return h; } uint64 gcd(uint64 a, uint64 b) { uint64 remainder; while (b != 0) { remainder = a % b; a = b; b = remainder; } return a; } uint64 factorize(int64 number){ int64 count, loop = 1; int64 x_fixed = 2, size = 2, x = 2, factor = 1; while (factor == 1) { for (count = 1; (count <= size) && (factor <= 1); count++) { x = (x * x + 1) % number; factor = gcd(abs(x - x_fixed), number); } size = 2 * size; x_fixed = x; loop = loop + 1; } return factor; } |