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

long long p1 = 37, p2 = 31, q1 = 1610612741, q2 = 805306457;

int main(){
    int n;
    scanf("%d", &n);
    char k;
    int c;
    k = getchar();
    while(!(k <= 'z' && k >= 'a'))
        k = getchar();
    long long h_a1 = 0, h_b1 = 0, h_a2 = 0, h_b2 = 0;
    long long pom1 = 1;
    long long pom2 = 1;
    while(true){
        c = k - 'a' + 1;
        h_a1 = (((h_a1 * p1) + c) % q1 + q1) % q1;
        h_b1 = ((c * pom1 + h_b1) % q1 + q1) % q1;
        h_a2 = (((h_a2 * p2) + c) % q2 + q2) % q2;
        h_b2 = ((c * pom2 + h_b2) % q2 + q2) % q2;
        pom1 = ((pom1 * p1) % q1 + q1) % q1;
        pom2 = ((pom2 * p2) % q2 + q2) % q2;
        k = getchar();
        if(!(k <= 'z' && k >= 'a'))
            break;
    }
    if(h_a1 == h_b1 && h_a2 == h_b2)
        printf("TAK\n");
    else
        printf("NIE\n");
}