#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"; } |
English