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

using namespace std;
using LL = long long;

const int mod1 = 1000000007;
const int mod2 = 1000000009;

int main()
{
	int n;
	cin >> n;

	int m = (n == 0 ? 10000000 : (n + 1) / 2);

	char c;
	cin >> c;

	int cnt = 1;
	deque<char> q = { c };

	LL hash11 = 0;
	LL hash12 = 0;
	LL hash21 = 0;
	LL hash22 = 0;
	LL h1 = 1;
	LL h2 = 1;

	while (cin >> c)
	{
		cnt++;

		if (cnt <= m)
			q.push_front(c);

		if (cnt % 2 == 0)
		{
			hash11 = (h1 * q.back() + hash11) % mod1;
			hash12 = (hash12 * 23 + c) % mod1;

			hash21 = (h2 * q.back() + hash21) % mod2;
			hash22 = (hash22 * 29 + c) % mod2;

			q.pop_back();
		}
		else
		{
			hash12 = (hash12 - (h1 * q.back() % mod1) + mod1) % mod1;
			hash12 = (hash12 * 23 + c) % mod1;

			hash22 = (hash22 - (h2 * q.back() % mod2) + mod2) % mod2;
			hash22 = (hash22 * 29 + c) % mod2;

			h1 = h1 * 23 % mod1;
			h2 = h2 * 29 % mod2;
		}
	}

	if (hash11 == hash12 && hash21 == hash22)
		cout << "TAK";
	else
		cout << "NIE";

	return 0;
}