#include <bits/stdc++.h> using namespace std; typedef unsigned uint; typedef unsigned long long ull; uint add(uint a, uint b, uint m) { return a+b < m ? a+b : a+b-m; } uint mul(uint a, uint b, uint m) { return (ull)a*b%m; } uint mpow(uint b, uint e, uint m) { uint r = 1; for (; e; e >>= 1) { if (e&1) r = mul(r, b, m); b = mul(b, b, m); } return r; } const pair<uint, uint> par[] = { //{1000000007, 630}, //{2000000011, 418}, //{2000000033, 358}, //{2000000063, 199}, //{2000012137, 623}, //{2000034583, 752}, {2000034629, 591}, {2005678937, 956}, {2008241371, 878}, {2147483647, 509}, }; uint h1[16], h2[16], p[16]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); const int k = sizeof(par)/sizeof(*par); int n; char c; for (int j = 0; j < k; ++j) p[j] = 1; cin >> n; while (cin >> c) { uint x = c-'0'; for (int j = 0; j < k; ++j) { uint m = par[j].first, a = par[j].second; h1[j] = add(mul(h1[j], a, m), x, m); h2[j] = add(h2[j], mul(p[j], x, m), m); p[j] = mul(p[j], a, m); } } for (int j = 0; j < k; ++j) { if (h1[j] != h2[j]) return cout << "NIE\n", 0; } cout << "TAK\n"; return 0; }
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 67 68 69 70 | #include <bits/stdc++.h> using namespace std; typedef unsigned uint; typedef unsigned long long ull; uint add(uint a, uint b, uint m) { return a+b < m ? a+b : a+b-m; } uint mul(uint a, uint b, uint m) { return (ull)a*b%m; } uint mpow(uint b, uint e, uint m) { uint r = 1; for (; e; e >>= 1) { if (e&1) r = mul(r, b, m); b = mul(b, b, m); } return r; } const pair<uint, uint> par[] = { //{1000000007, 630}, //{2000000011, 418}, //{2000000033, 358}, //{2000000063, 199}, //{2000012137, 623}, //{2000034583, 752}, {2000034629, 591}, {2005678937, 956}, {2008241371, 878}, {2147483647, 509}, }; uint h1[16], h2[16], p[16]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); const int k = sizeof(par)/sizeof(*par); int n; char c; for (int j = 0; j < k; ++j) p[j] = 1; cin >> n; while (cin >> c) { uint x = c-'0'; for (int j = 0; j < k; ++j) { uint m = par[j].first, a = par[j].second; h1[j] = add(mul(h1[j], a, m), x, m); h2[j] = add(h2[j], mul(p[j], x, m), m); p[j] = mul(p[j], a, m); } } for (int j = 0; j < k; ++j) { if (h1[j] != h2[j]) return cout << "NIE\n", 0; } cout << "TAK\n"; return 0; } |