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
#include <iostream>
#include <cmath>
#include <stdio.h>

using namespace std;


int main(){
    long long n,i=0;
    char l;
    cin >> n;
    int p=31;
    long long m = 1e9+9;    
    long long hash1=0,hash2=0;
    long long ppower=1,N_ippower=197737404,_ippower=1,ppower_1=838709685;
    long long mb = 1e9+21;
    long long hash1b=0,hash2b=0;
    long long ppowerb=1,_ippowerb=1,ppower_1b=161290326;

    while(scanf(" %c",&l)!=EOF) {

    hash1= (hash1+(l - 'a'+1)*ppower)%m;
    ppower= (ppower*p)%m;
//    cout << int(l-'a'+1) <<endl;

    hash2= (hash2 + (l - 'a' +1)*_ippower)%m;
    _ippower = (_ippower*ppower_1)%m;

//    cout <<"i" << i <<" ppower= " << ppower << "_ippower=" << _ippower<<" hash1="<<hash1 << " hash2="<<hash2<<" roznicza= " << (-hash1+hash2)%m<<endl;
    hash1b= (hash1b+(l - 'a'+1)*ppowerb)%mb;
    ppowerb= (ppowerb*p)%mb;
//    cout << int(l-'a'+1) <<endl;

    hash2b= (hash2b + (l - 'a' +1)*_ippowerb)%mb;
    _ippowerb = (_ippowerb*ppower_1b)%mb;

    i++;
    }
    ppower=(ppower*ppower_1)%m;
    hash2=(hash2*ppower)%m;

    ppowerb=(ppowerb*ppower_1b)%mb;
    hash2b=(hash2b*ppowerb)%mb;

//  cout <<"hahs1="<<hash1 << " hash2="<<hash2<<" roznicza= " << (-hash1+hash2)%m<<endl;
    if((-hash1+hash2)%m==0&&(-hash1b+hash2b)%mb==0) cout << "TAK"<<endl;
    else cout<<"NIE"<<endl;

    return 0;
}