#include <bits/stdc++.h> #define FOR(i, a, b) for(int i = (a); i < (b); ++i) #define FORD(i, a, b) for(int i = (a); i >= (b); --i) #define VAR(v, i) __typeof(i) v=(i) #define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i) #define all(v) (v).begin(),(v).end() #define PII pair<int,int> #define mp make_pair #define st first #define nd second #define pb push_back #define lint long long int #define VI vector<int> #define debug(x) {cout <<#x <<" = " <<x <<endl; } #define debug2(x,y) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y <<endl; } #define debug3(x,y,z) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y << ", " << #z << " = " << z <<endl; } #define debugv(x) {{cout <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<endl; }} #define debugt(t,n) {{cerr <<#t <<" = "; FOR(it,0,(n)) cerr <<t[it] <<", "; cerr <<endl; }} #define make( x) int (x); scanf("%d",&(x)); #define make2( x, y) int (x), (y); scanf("%d%d",&(x),&(y)); #define make3(x, y, z) int (x), (y), (z); scanf("%d%d%d",&(x),&(y),&(z)); #define make4(x, y, z, t) int (x), (y), (z), (t); scanf("%d%d%d%d",&(x),&(y),&(z),&(t)); #define makev(v,n) VI (v); FOR(i,0,(n)) { make(a); (v).pb(a);} #define IOS ios_base::sync_with_stdio(0) #define HEAP priority_queue #define read( x) scanf("%d",&(x)); #define read2( x, y) scanf("%d%d",&(x),&(y)); #define read3(x, y, z) scanf("%d%d%d",&(x),&(y),&(z)); #define read4(x, y, z, t) scanf("%d%d%d%d",&(x),&(y),&(z),&(t)); #define readv(v,n) FOR(i,0,(n)) { make(a); (v).pb(a);} #define jeb() fflush(stdout); using namespace std; int TESTS = 3; int bazy[] = { 100, 123, 315, 421, 4901, 45903, 49320}; int sol[] = {41, 12, 271, 300, 2137, 35000, 40000}; int p[] = {1000004023,1000004059,1000004099,1000004119,1000004123,1000004207,1000004233}; int h[] = {0,0,0,0,0,0,0}; int hr[] = {0,0,0,0,0,0,0}; int powy[] = {1,1,1,1,1,1,1}; int main() { int n; scanf("%d",&n); char C = getchar(); while (C<'a' || C>'z') C = getchar(); do { int ja = C-'a'; FOR(i,0,TESTS) { h[i] = (h[i] * 1LL * bazy[i] + (ja + sol[i])) % p[i]; hr[i] = (hr[i] + powy[i] * 1LL * (ja + sol[i])) % p[i]; powy[i] = (powy[i] * 1LL * bazy[i]) % p[i]; } C = getchar(); } while (C!='\n'); bool ok = true; FOR(i,0,TESTS) { if (h[i] != hr[i]) ok = false; } if (ok) printf("TAK\n"); else printf("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 63 64 65 66 67 68 69 | #include <bits/stdc++.h> #define FOR(i, a, b) for(int i = (a); i < (b); ++i) #define FORD(i, a, b) for(int i = (a); i >= (b); --i) #define VAR(v, i) __typeof(i) v=(i) #define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i) #define all(v) (v).begin(),(v).end() #define PII pair<int,int> #define mp make_pair #define st first #define nd second #define pb push_back #define lint long long int #define VI vector<int> #define debug(x) {cout <<#x <<" = " <<x <<endl; } #define debug2(x,y) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y <<endl; } #define debug3(x,y,z) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y << ", " << #z << " = " << z <<endl; } #define debugv(x) {{cout <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<endl; }} #define debugt(t,n) {{cerr <<#t <<" = "; FOR(it,0,(n)) cerr <<t[it] <<", "; cerr <<endl; }} #define make( x) int (x); scanf("%d",&(x)); #define make2( x, y) int (x), (y); scanf("%d%d",&(x),&(y)); #define make3(x, y, z) int (x), (y), (z); scanf("%d%d%d",&(x),&(y),&(z)); #define make4(x, y, z, t) int (x), (y), (z), (t); scanf("%d%d%d%d",&(x),&(y),&(z),&(t)); #define makev(v,n) VI (v); FOR(i,0,(n)) { make(a); (v).pb(a);} #define IOS ios_base::sync_with_stdio(0) #define HEAP priority_queue #define read( x) scanf("%d",&(x)); #define read2( x, y) scanf("%d%d",&(x),&(y)); #define read3(x, y, z) scanf("%d%d%d",&(x),&(y),&(z)); #define read4(x, y, z, t) scanf("%d%d%d%d",&(x),&(y),&(z),&(t)); #define readv(v,n) FOR(i,0,(n)) { make(a); (v).pb(a);} #define jeb() fflush(stdout); using namespace std; int TESTS = 3; int bazy[] = { 100, 123, 315, 421, 4901, 45903, 49320}; int sol[] = {41, 12, 271, 300, 2137, 35000, 40000}; int p[] = {1000004023,1000004059,1000004099,1000004119,1000004123,1000004207,1000004233}; int h[] = {0,0,0,0,0,0,0}; int hr[] = {0,0,0,0,0,0,0}; int powy[] = {1,1,1,1,1,1,1}; int main() { int n; scanf("%d",&n); char C = getchar(); while (C<'a' || C>'z') C = getchar(); do { int ja = C-'a'; FOR(i,0,TESTS) { h[i] = (h[i] * 1LL * bazy[i] + (ja + sol[i])) % p[i]; hr[i] = (hr[i] + powy[i] * 1LL * (ja + sol[i])) % p[i]; powy[i] = (powy[i] * 1LL * bazy[i]) % p[i]; } C = getchar(); } while (C!='\n'); bool ok = true; FOR(i,0,TESTS) { if (h[i] != hr[i]) ok = false; } if (ok) printf("TAK\n"); else printf("NIE\n"); } |