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
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int MAXI = int(20e6);
const LL A = 911382323;
const LL B = 972663749;

queue<char> q;

int main()
{
	ios_base::sync_with_stdio(0);
//	cin.tie(0);
	int n;
	cin >> n;
	if(n == 0)
		n = MAXI;
	int up = n/2 + 1;
	LL p, d;
	LL zA = 1;
	bool odp = 1;
	int i = 0;
	char c;
	while(cin >> c)
	{
		i++;
		if(i == 1)
			p = c;
		else if(i == 2)
		{
			d = c;
			odp = (p==d);
			q.push(d);
		}
		else
		{
			LL x = LL(q.front());
			if(i <= up)
				q.push(c);
			if(i % 2 == 1)
				d = (A*((d - x * zA)%B + B)%B+c)%B;
			else
			{
				q.pop();
				zA = (zA * A) % B;
				p = (p + zA * x)%B;
				d = (d * A + c)%B;
			}
			odp = (p==d);
		}
	}
	cout << (odp ? "TAK" : "NIE");
}