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
#include <iostream>

constexpr unsigned long long int MOD = 4294967291; // first prime number below 2^32
constexpr unsigned long long int FACTOR = 4294967279; // first prime number below MOD
constexpr auto MAX_SIZE = 'z' - 'a' + 1;

bool isPalindrom(unsigned long long int* hash1, unsigned long long int* hash2)
{
    for (int i = 0; i < MAX_SIZE; ++i) {
        if (hash1[i] != hash2[i])
            return false;
    }
    return true;
}

void process(unsigned long long int* hash1, unsigned long long int* hash2, unsigned long long int& power, unsigned char value)
{
    for (int i = 0; i < MAX_SIZE; ++i) {
        hash2[i] = (hash2[i] * FACTOR) % MOD;
    }
    hash1[value] = (hash1[value] + power) % MOD;
    hash2[value] = (hash2[value] + 1) % MOD;
    power = (power * FACTOR) % MOD;
}

int main()
{
    int n;
    unsigned long long int hash1[MAX_SIZE], hash2[MAX_SIZE], power = 1;
    unsigned char value;
    for (int i = 0; i < MAX_SIZE; ++i) {
        hash1[i] = 0;
        hash2[i] = 0;
    }

    std::cin >> n;
    while (std::cin >> value) {
        process(hash1, hash2, power, value - 'a');
    }

    if (isPalindrom(hash1, hash2)) {
        std::cout << "TAK" << std::endl;
    } else {
        std::cout << "NIE" << std::endl;
    }

    return 0;
}