#include <iostream> using namespace std; typedef long long ll; const int hn = 10; ll a[hn] = { 67867967, 12211937, 23010067, 91744613, 94008721, 40544951, 38567099, 23496587, 23596147, 66666667 }; ll m[hn] = { 69522569, 14921969, 15141163, 92364991, 37171397, 68956417, 66410849, 66612223, 39766409, 64987523 }; ll h[hn][2]; ll ap[hn]; int main() { ios_base::sync_with_stdio(0); int i; char c; cin >> i; for (i = 0; i < hn; i++) ap[i] = 1; while (true) { cin >> c; if (cin.eof()) break; for (i = 0; i < hn; i++) { h[i][0] = (a[i] * h[i][0] + (ll)c) % m[i]; h[i][1] = (h[i][1] + (ll)c * ap[i]) % m[i]; ap[i] = (ap[i] * a[i]) % m[i]; } } for (i = 0; i < hn; i++) { if (h[i][0] != h[i][1]) { cout << "NIE" << endl; return 0; } } cout << "TAK" << endl; 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 | #include <iostream> using namespace std; typedef long long ll; const int hn = 10; ll a[hn] = { 67867967, 12211937, 23010067, 91744613, 94008721, 40544951, 38567099, 23496587, 23596147, 66666667 }; ll m[hn] = { 69522569, 14921969, 15141163, 92364991, 37171397, 68956417, 66410849, 66612223, 39766409, 64987523 }; ll h[hn][2]; ll ap[hn]; int main() { ios_base::sync_with_stdio(0); int i; char c; cin >> i; for (i = 0; i < hn; i++) ap[i] = 1; while (true) { cin >> c; if (cin.eof()) break; for (i = 0; i < hn; i++) { h[i][0] = (a[i] * h[i][0] + (ll)c) % m[i]; h[i][1] = (h[i][1] + (ll)c * ap[i]) % m[i]; ap[i] = (ap[i] * a[i]) % m[i]; } } for (i = 0; i < hn; i++) { if (h[i][0] != h[i][1]) { cout << "NIE" << endl; return 0; } } cout << "TAK" << endl; return 0; } |