#include <bits/stdc++.h> #define ll long long #define debug if(0) const ll MOD = 1e9+21; ll x[3] = {31, 59, 101}; ll pot[3] = {1, 1, 1}; ll H[3]; // hash ll HR[3]; // hash reverse int main(){ int n; std::cin >> n; char c; while (std::cin >> c){ for (int i = 0; i < 3; i++){ H[i] = (H[i] + (ll)(c-'a'+1) * pot[i]) % MOD; HR[i] = (HR[i] * x[i] + (ll)(c-'a'+1)) % MOD; pot[i] = (pot[i] * x[i]) % MOD; } debug{ for (int i = 0; i < 3; i++) std::cout << "H[" << i << "]: " << H[i] << ", HR[" << i << "]: " << HR[i] << "\n"; } } (H[0] == HR[0] && H[1] == HR[1] && H[2] == HR[2]) ? std::cout << "TAK\n" : std::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 | #include <bits/stdc++.h> #define ll long long #define debug if(0) const ll MOD = 1e9+21; ll x[3] = {31, 59, 101}; ll pot[3] = {1, 1, 1}; ll H[3]; // hash ll HR[3]; // hash reverse int main(){ int n; std::cin >> n; char c; while (std::cin >> c){ for (int i = 0; i < 3; i++){ H[i] = (H[i] + (ll)(c-'a'+1) * pot[i]) % MOD; HR[i] = (HR[i] * x[i] + (ll)(c-'a'+1)) % MOD; pot[i] = (pot[i] * x[i]) % MOD; } debug{ for (int i = 0; i < 3; i++) std::cout << "H[" << i << "]: " << H[i] << ", HR[" << i << "]: " << HR[i] << "\n"; } } (H[0] == HR[0] && H[1] == HR[1] && H[2] == HR[2]) ? std::cout << "TAK\n" : std::cout << "NIE\n"; } |