#include <bits/stdc++.h> using namespace std; #define int long long int fastpow(int x, int p, int mod) { if (p == 0) return 1; int y = fastpow(x, p/2, mod); y = y * y % mod; if (p % 2 == 1) y = y * x % mod; return y; } struct Tester { int x, y, mod; int hx, hy; int n = 0; Tester(int x, int y, int mod):x(x), y(y), mod(mod) { assert((x * y % mod) == 1); hx = 0; hy = 0; } inline void put(int c) { hx = (hx * x + c) % mod; hy = (hy * y + c) % mod; n++; } void process() { hy = hy * fastpow(x, n - 1, mod) % mod;; } bool isok() { cerr << hx << " " << hy << "\n"; return hx == hy; } }; signed main() { ios_base::sync_with_stdio(0); srand(time(NULL)); int n; cin >> n; char c; vector<int> mapping(10000); for (int i = 0; i < 10000; ++i) { mapping[i] = 100 + 6*i + rand()%3; } random_shuffle(begin(mapping), end(mapping)); vector<Tester> v; v.push_back(Tester(999999, 387512391, 1e9 + 9)); v.push_back(Tester(9971, 834620405, 1e9 + 7)); v.push_back(Tester(7320394, 103838873, 111191111)); while (cin >> c) { for (auto &x: v) x.put(mapping[c]); } for (auto &x: v) x.process(); bool ok = true; for (auto &x: v) ok = ok && x.isok(); if (ok) cout << "TAK\n"; else cout << "NIE\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 71 72 73 | #include <bits/stdc++.h> using namespace std; #define int long long int fastpow(int x, int p, int mod) { if (p == 0) return 1; int y = fastpow(x, p/2, mod); y = y * y % mod; if (p % 2 == 1) y = y * x % mod; return y; } struct Tester { int x, y, mod; int hx, hy; int n = 0; Tester(int x, int y, int mod):x(x), y(y), mod(mod) { assert((x * y % mod) == 1); hx = 0; hy = 0; } inline void put(int c) { hx = (hx * x + c) % mod; hy = (hy * y + c) % mod; n++; } void process() { hy = hy * fastpow(x, n - 1, mod) % mod;; } bool isok() { cerr << hx << " " << hy << "\n"; return hx == hy; } }; signed main() { ios_base::sync_with_stdio(0); srand(time(NULL)); int n; cin >> n; char c; vector<int> mapping(10000); for (int i = 0; i < 10000; ++i) { mapping[i] = 100 + 6*i + rand()%3; } random_shuffle(begin(mapping), end(mapping)); vector<Tester> v; v.push_back(Tester(999999, 387512391, 1e9 + 9)); v.push_back(Tester(9971, 834620405, 1e9 + 7)); v.push_back(Tester(7320394, 103838873, 111191111)); while (cin >> c) { for (auto &x: v) x.put(mapping[c]); } for (auto &x: v) x.process(); bool ok = true; for (auto &x: v) ok = ok && x.isok(); if (ok) cout << "TAK\n"; else cout << "NIE\n"; return 0; } |