#include <cstdio> #include <cstdlib> #include <cstdint> template<uint64_t MUL, uint64_t MOD> struct twohash { private: uint64_t forwards, backwards; uint64_t power; public: twohash() : forwards(0), backwards(0), power(1) {} inline void advance(uint64_t x) { backwards = (x + MUL * backwards) % MOD; forwards = (forwards + x * power) % MOD; power = (power * MUL) % MOD; } inline bool hasMatch() const { return forwards == backwards; } }; inline bool isLetter(int c) { return c >= 'a' && c <= 'z'; } int main() { int n; scanf("%d", &n); int c; while (!isLetter(c = getchar())) {} twohash<26ULL, 46132598700804613ULL> h1; twohash<26ULL, 179106878071766873ULL> h2; do { h1.advance(c - 'a'); h2.advance(c - 'a'); } while (isLetter(c = getchar())); puts((h1.hasMatch() && h2.hasMatch()) ? "TAK" : "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 | #include <cstdio> #include <cstdlib> #include <cstdint> template<uint64_t MUL, uint64_t MOD> struct twohash { private: uint64_t forwards, backwards; uint64_t power; public: twohash() : forwards(0), backwards(0), power(1) {} inline void advance(uint64_t x) { backwards = (x + MUL * backwards) % MOD; forwards = (forwards + x * power) % MOD; power = (power * MUL) % MOD; } inline bool hasMatch() const { return forwards == backwards; } }; inline bool isLetter(int c) { return c >= 'a' && c <= 'z'; } int main() { int n; scanf("%d", &n); int c; while (!isLetter(c = getchar())) {} twohash<26ULL, 46132598700804613ULL> h1; twohash<26ULL, 179106878071766873ULL> h2; do { h1.advance(c - 'a'); h2.advance(c - 'a'); } while (isLetter(c = getchar())); puts((h1.hasMatch() && h2.hasMatch()) ? "TAK" : "NIE"); return 0; } |