#include<cstdio> #define mod1 1000000009 #define mod2 1000696969 #define mno1 31 #define mno2 29 long long h1_L,h2_L,h1_R,h2_R,n; char c; long long potmod(long long a,long long pow,long long mod) { if(pow==0)return 1; if(pow&1)return (potmod(a,pow-1,mod)*a)%mod; else { long long x=potmod(a,pow/2,mod); return (x*x)%mod; } } int main() { scanf("%lld\n",&n); int i; while(1) { scanf("%c",&c); if(c=='\n')break; c-='a'; h1_L=(h1_L*mno1+c)%mod1; h2_L=(h2_L*mno2+c)%mod2; h1_R=(h1_R+c*potmod(mno1,i,mod1))%mod1; h2_R=(h2_R+c*potmod(mno2,i,mod2))%mod2; i++; } if(h1_L==h1_R&&h2_L==h2_R)printf("TAK"); else printf("NIE"); }
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 | #include<cstdio> #define mod1 1000000009 #define mod2 1000696969 #define mno1 31 #define mno2 29 long long h1_L,h2_L,h1_R,h2_R,n; char c; long long potmod(long long a,long long pow,long long mod) { if(pow==0)return 1; if(pow&1)return (potmod(a,pow-1,mod)*a)%mod; else { long long x=potmod(a,pow/2,mod); return (x*x)%mod; } } int main() { scanf("%lld\n",&n); int i; while(1) { scanf("%c",&c); if(c=='\n')break; c-='a'; h1_L=(h1_L*mno1+c)%mod1; h2_L=(h2_L*mno2+c)%mod2; h1_R=(h1_R+c*potmod(mno1,i,mod1))%mod1; h2_R=(h2_R+c*potmod(mno2,i,mod2))%mod2; i++; } if(h1_L==h1_R&&h2_L==h2_R)printf("TAK"); else printf("NIE"); } |