//Daniel Grzegorzewski #include <bits/stdc++.h> #pragma GCC optimize("O3") #define MP make_pair #define PB push_back #define ST first #define ND second #define int long long using namespace std; typedef pair<int, int> PII; typedef vector<int> VI; typedef vector<PII> VII; typedef long long LL; void init_ios() { ios_base::sync_with_stdio(0); cin.tie(0); } const int I = 4; const int mod[I] = {(int)1e9-117, (int)1e9-107, (int)1e9-71, (int)1e9-63}; const int X = 341; int n, p[I] = {1, 1, 1, 1}, h1[I], h2[I]; char c; signed main() { init_ios(); cin >> n; while (cin >> c) { for (int i = 0; i < I; ++i) { h1[i] = h1[i]*X + c; if (h1[i] >= mod[i]) h1[i] %= mod[i]; h2[i] += c*p[i]; if (h2[i] >= mod[i]) h2[i] %= mod[i]; p[i] = X*p[i]; if (p[i] >= mod[i]) p[i] %= mod[i]; } } bool eq = true; for (int i = 0; i < I; ++i) if (h1[i] != h2[i]) eq = false; if (eq) cout<<"TAK\n"; else cout<<"NIE\n"; }
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 | //Daniel Grzegorzewski #include <bits/stdc++.h> #pragma GCC optimize("O3") #define MP make_pair #define PB push_back #define ST first #define ND second #define int long long using namespace std; typedef pair<int, int> PII; typedef vector<int> VI; typedef vector<PII> VII; typedef long long LL; void init_ios() { ios_base::sync_with_stdio(0); cin.tie(0); } const int I = 4; const int mod[I] = {(int)1e9-117, (int)1e9-107, (int)1e9-71, (int)1e9-63}; const int X = 341; int n, p[I] = {1, 1, 1, 1}, h1[I], h2[I]; char c; signed main() { init_ios(); cin >> n; while (cin >> c) { for (int i = 0; i < I; ++i) { h1[i] = h1[i]*X + c; if (h1[i] >= mod[i]) h1[i] %= mod[i]; h2[i] += c*p[i]; if (h2[i] >= mod[i]) h2[i] %= mod[i]; p[i] = X*p[i]; if (p[i] >= mod[i]) p[i] %= mod[i]; } } bool eq = true; for (int i = 0; i < I; ++i) if (h1[i] != h2[i]) eq = false; if (eq) cout<<"TAK\n"; else cout<<"NIE\n"; } |