#include <bits/stdc++.h> using namespace std; typedef long long ll; struct Hash{ ll B, MOD, VAL = 0, IL = 1; void init(ll b, ll m){ B = b; MOD = m; } void add(ll a){ a = (a*IL)%MOD; VAL = (VAL+a)%MOD; IL = (IL*B)%MOD; } long long getHash(){ return VAL; } }; struct HashR{ ll B, MOD, VAL = 0; void init(ll b, ll m){ B = b; MOD = m; } void add(ll a){ VAL = (VAL*B + a)%MOD; } long long getHash(){ return VAL; } }; int main(){ ios_base::sync_with_stdio(0); int n; cin >> n; Hash HA; HashR HAr; HA.init(513083, 1e12+39); HAr.init(513083, 1e12+39); Hash HB; HashR HBr; HB.init(417187, 1e12-11); HBr.init(417187, 1e12-11); char ch; while(cin >> ch){ ll a = ch-'a'+1; HA.add(a); HAr.add(a); HB.add(a); HBr.add(a); } if(HA.getHash() == HAr.getHash() && HB.getHash() == HBr.getHash()) cout << "TAK\n"; else 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 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 | #include <bits/stdc++.h> using namespace std; typedef long long ll; struct Hash{ ll B, MOD, VAL = 0, IL = 1; void init(ll b, ll m){ B = b; MOD = m; } void add(ll a){ a = (a*IL)%MOD; VAL = (VAL+a)%MOD; IL = (IL*B)%MOD; } long long getHash(){ return VAL; } }; struct HashR{ ll B, MOD, VAL = 0; void init(ll b, ll m){ B = b; MOD = m; } void add(ll a){ VAL = (VAL*B + a)%MOD; } long long getHash(){ return VAL; } }; int main(){ ios_base::sync_with_stdio(0); int n; cin >> n; Hash HA; HashR HAr; HA.init(513083, 1e12+39); HAr.init(513083, 1e12+39); Hash HB; HashR HBr; HB.init(417187, 1e12-11); HBr.init(417187, 1e12-11); char ch; while(cin >> ch){ ll a = ch-'a'+1; HA.add(a); HAr.add(a); HB.add(a); HBr.add(a); } if(HA.getHash() == HAr.getHash() && HB.getHash() == HBr.getHash()) cout << "TAK\n"; else cout << "NIE\n"; } |