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;
}