#include <bits/stdc++.h> using namespace std; #define G 3 int p[]={999999929,1000000007,999999893,9999991,10000019,10000079,99999959,99999971,99999989,1000003,999999937}; int base[]={256,65536,128,2147483647,192,32768,16386,4096,2048,2014,1048576}; long long a[G],b[G],bp[G]; int main() { ios_base::sync_with_stdio(0); int n; cin >>n; char z; for (int i=0;i<G;i++) bp[i]=1; while (cin >> z) { //for (int i=0;i<20000000;i++) { //z = rand()%26+'a'; for (int i=0;i<G;i++) { a[i] = (a[i]*base[i]+z)%p[i]; b[i] = (b[i] + bp[i]*z)%p[i]; bp[i]= (bp[i]*base[i])%p[i]; } } bool ok=true; for (int i=0;ok && i<G;i++){ ok = ok && (a[i]==b[i]); //cout << a[i]<<" "<<b[i]<<endl; } cout << (ok ? "TAK" : "NIE") <<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 | #include <bits/stdc++.h> using namespace std; #define G 3 int p[]={999999929,1000000007,999999893,9999991,10000019,10000079,99999959,99999971,99999989,1000003,999999937}; int base[]={256,65536,128,2147483647,192,32768,16386,4096,2048,2014,1048576}; long long a[G],b[G],bp[G]; int main() { ios_base::sync_with_stdio(0); int n; cin >>n; char z; for (int i=0;i<G;i++) bp[i]=1; while (cin >> z) { //for (int i=0;i<20000000;i++) { //z = rand()%26+'a'; for (int i=0;i<G;i++) { a[i] = (a[i]*base[i]+z)%p[i]; b[i] = (b[i] + bp[i]*z)%p[i]; bp[i]= (bp[i]*base[i])%p[i]; } } bool ok=true; for (int i=0;ok && i<G;i++){ ok = ok && (a[i]==b[i]); //cout << a[i]<<" "<<b[i]<<endl; } cout << (ok ? "TAK" : "NIE") <<endl; return 0; } |