#include <iostream> using namespace std; unsigned long long hashNormalny1; unsigned long long hashNormalny2; unsigned long long hashOdwrocony1; unsigned long long hashOdwrocony2; const unsigned long long p1 = 29; unsigned long long odwrotnoscP1; const unsigned long long p2 = 31; unsigned long long odwrotnoscP2; const unsigned long long mod1 = 1000 * 1000 * 1000 + 7; const unsigned long long mod2 = 1000 * 1000 * 1000 + 9; const int NMAX = 20000000; long long potModulo(long long x, long long c, long long mod) { if(c == 0) return 1; if(c % 2 == 1) return (x * potModulo(x, c - 1, mod)) % mod; long long t = potModulo(x, c / 2, mod); return (t * t) % mod; } int naLiczbe(char c) { return c - 'a' + 1; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); odwrotnoscP1 = potModulo(p1, mod1 - 2, mod1); odwrotnoscP2 = potModulo(p2, mod2 - 2, mod2); int n; cin >> n; int i = 0; char t; long long aktualneOdwroconeP1 = potModulo(p1, NMAX - 1, mod1); long long aktualneOdwroconeP2 = potModulo(p2, NMAX - 1, mod2); long long aktualneNormalneP1 = 1; long long aktualneNormalneP2 = 1; while(cin >> t) { long long tLiczba = naLiczbe(t); hashNormalny1 = (hashNormalny1 + aktualneNormalneP1 * tLiczba) % mod1; hashNormalny2 = (hashNormalny2 + aktualneNormalneP2 * tLiczba) % mod2; hashOdwrocony1 = (hashOdwrocony1 + aktualneOdwroconeP1 * tLiczba) % mod1; hashOdwrocony2 = (hashOdwrocony2 + aktualneOdwroconeP2 * tLiczba) % mod2; aktualneOdwroconeP1 = (aktualneOdwroconeP1 * odwrotnoscP1) % mod1; aktualneOdwroconeP2 = (aktualneOdwroconeP2 * odwrotnoscP2) % mod2; aktualneNormalneP1 = (aktualneNormalneP1 * p1) % mod1; aktualneNormalneP2 = (aktualneNormalneP2 * p2) % mod2; i++; } hashNormalny1 = (hashNormalny1 * potModulo(p1, NMAX - i, mod1)) % mod1; hashNormalny2 = (hashNormalny2 * potModulo(p2, NMAX - i, mod2)) % mod2; if(hashNormalny1 == hashOdwrocony1 && hashNormalny2 == hashOdwrocony2) cout << "TAK"; else cout << "NIE"; 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 74 75 76 77 78 | #include <iostream> using namespace std; unsigned long long hashNormalny1; unsigned long long hashNormalny2; unsigned long long hashOdwrocony1; unsigned long long hashOdwrocony2; const unsigned long long p1 = 29; unsigned long long odwrotnoscP1; const unsigned long long p2 = 31; unsigned long long odwrotnoscP2; const unsigned long long mod1 = 1000 * 1000 * 1000 + 7; const unsigned long long mod2 = 1000 * 1000 * 1000 + 9; const int NMAX = 20000000; long long potModulo(long long x, long long c, long long mod) { if(c == 0) return 1; if(c % 2 == 1) return (x * potModulo(x, c - 1, mod)) % mod; long long t = potModulo(x, c / 2, mod); return (t * t) % mod; } int naLiczbe(char c) { return c - 'a' + 1; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); odwrotnoscP1 = potModulo(p1, mod1 - 2, mod1); odwrotnoscP2 = potModulo(p2, mod2 - 2, mod2); int n; cin >> n; int i = 0; char t; long long aktualneOdwroconeP1 = potModulo(p1, NMAX - 1, mod1); long long aktualneOdwroconeP2 = potModulo(p2, NMAX - 1, mod2); long long aktualneNormalneP1 = 1; long long aktualneNormalneP2 = 1; while(cin >> t) { long long tLiczba = naLiczbe(t); hashNormalny1 = (hashNormalny1 + aktualneNormalneP1 * tLiczba) % mod1; hashNormalny2 = (hashNormalny2 + aktualneNormalneP2 * tLiczba) % mod2; hashOdwrocony1 = (hashOdwrocony1 + aktualneOdwroconeP1 * tLiczba) % mod1; hashOdwrocony2 = (hashOdwrocony2 + aktualneOdwroconeP2 * tLiczba) % mod2; aktualneOdwroconeP1 = (aktualneOdwroconeP1 * odwrotnoscP1) % mod1; aktualneOdwroconeP2 = (aktualneOdwroconeP2 * odwrotnoscP2) % mod2; aktualneNormalneP1 = (aktualneNormalneP1 * p1) % mod1; aktualneNormalneP2 = (aktualneNormalneP2 * p2) % mod2; i++; } hashNormalny1 = (hashNormalny1 * potModulo(p1, NMAX - i, mod1)) % mod1; hashNormalny2 = (hashNormalny2 * potModulo(p2, NMAX - i, mod2)) % mod2; if(hashNormalny1 == hashOdwrocony1 && hashNormalny2 == hashOdwrocony2) cout << "TAK"; else cout << "NIE"; return 0; } |