#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef long double LD; typedef pair < int, int > PII; typedef pair < LL, LL > PLL; typedef pair < LD, LD > PDD; #define _upgrade ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define all(x) (x).begin(), (x).end() #define sz(x) (int)(x).size() template < typename _T > inline void _DBG(const char *s, _T x) { cerr << s << " = " << x << "\n"; } template < typename _T, typename... args > void _DBG(const char *s, _T x, args... a) { while(*s != ',') cerr << *s++; cerr << " = " << x << ','; _DBG(s + 1, a...); } #ifdef LOCAL #define DBG(...) _DBG(#__VA_ARGS__, __VA_ARGS__) #define __gcd gcd #else #define DBG(...) (__VA_ARGS__) #define cerr if(0) cout #endif // ********************** CODE ********************** // typedef unsigned long long ULL; LL pre[5], suf[5], mul[5], base[5]; const int mod[5] = {1000000007, 1000000207, 961748941, 982451653, 1000000009}; int main() { srand(0); const int k = 2; int buf; scanf("%d", &buf); for(int i = 0; i < k; i++) { base[i] = 30 + rand() % 20; mul[i] = 1; } char z = getchar_unlocked(); z = getchar_unlocked(); while('a' <= z && z <= 'z') { z -= ('a' - 1); for(int i = 0; i < k; i++) { suf[i] = ((LL)suf[i] * base[i] + z) % mod[i]; pre[i] = ((LL)pre[i] + (LL)mul[i] * z) % mod[i]; mul[i] = ((LL)mul[i] * base[i]) % mod[i]; } z = getchar_unlocked(); } for(int i = 0; i < k; i++) { if(pre[i] != suf[i]) { puts("NIE"); return 0; } } puts("TAK"); 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 | #include <bits/stdc++.h> using namespace std; typedef long long LL; typedef long double LD; typedef pair < int, int > PII; typedef pair < LL, LL > PLL; typedef pair < LD, LD > PDD; #define _upgrade ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define all(x) (x).begin(), (x).end() #define sz(x) (int)(x).size() template < typename _T > inline void _DBG(const char *s, _T x) { cerr << s << " = " << x << "\n"; } template < typename _T, typename... args > void _DBG(const char *s, _T x, args... a) { while(*s != ',') cerr << *s++; cerr << " = " << x << ','; _DBG(s + 1, a...); } #ifdef LOCAL #define DBG(...) _DBG(#__VA_ARGS__, __VA_ARGS__) #define __gcd gcd #else #define DBG(...) (__VA_ARGS__) #define cerr if(0) cout #endif // ********************** CODE ********************** // typedef unsigned long long ULL; LL pre[5], suf[5], mul[5], base[5]; const int mod[5] = {1000000007, 1000000207, 961748941, 982451653, 1000000009}; int main() { srand(0); const int k = 2; int buf; scanf("%d", &buf); for(int i = 0; i < k; i++) { base[i] = 30 + rand() % 20; mul[i] = 1; } char z = getchar_unlocked(); z = getchar_unlocked(); while('a' <= z && z <= 'z') { z -= ('a' - 1); for(int i = 0; i < k; i++) { suf[i] = ((LL)suf[i] * base[i] + z) % mod[i]; pre[i] = ((LL)pre[i] + (LL)mul[i] * z) % mod[i]; mul[i] = ((LL)mul[i] * base[i]) % mod[i]; } z = getchar_unlocked(); } for(int i = 0; i < k; i++) { if(pre[i] != suf[i]) { puts("NIE"); return 0; } } puts("TAK"); return 0; } |