//#pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; #define ll long long #define ld long double #define pi pair<int,int> #define pd pair<ld,ld> #define ft first #define sd second #define st first #define nd second #define mp make_pair #define pb push_back #define eb emplace_back #define FOR(i,a,b) for(int i=(a); i<=(b);i++) #define F(i,a,b) FOR(i,(a),(b)-1) #define REV(i,a,b) for(int i=(a); i>=(b);i--) #define VI vector<int> #define VPI vector<pi> #define VPD vector<pd> #define PI 3.14159265 #define all(x) (x).begin(), (x).end() #define sz(a) (int)((a).size()) #define int long long template<class TH> void _dbg(const char *sdbg, TH h){cerr<<sdbg<<"="<<h<<"\n";} template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) { while(*sdbg!=',')cerr<<*sdbg++;cerr<<"="<<h<<","; _dbg(sdbg+1, a...); } #define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__) const long long inf = 1000*1000*1000+7; const long long inf2 = 1000*1000*1000+9; const long long INF = LLONG_MAX; const long long MOD = inf; const long long P = 997; const long long N = 1e6+10, base=1<<19; int Mul(int _a, int _b, int _MOD=MOD){return _a*_b%_MOD;} int Pow(int _a, int _b, int _MOD=MOD){int _pom = 1;for(;_b;_b/=2,_a=Mul(_a,_a,_MOD)){if(_b&1)_pom=Mul(_pom,_a,_MOD);}return _pom;} void solve(){ int n; cin>>n; char c; int przod0=0,tyl0=0,pomP0=1; int przod1=0,tyl1=0,pomP1=1; while(cin>>c) { przod0 = (przod0 * P + c)%inf; tyl0 = (tyl0 + c * pomP0)%inf; przod1 = (przod1 * P + c)%inf2; tyl1 = (tyl1 + c * pomP1)%inf2; pomP0 = Mul(pomP0, P); pomP1 = Mul(pomP1, P,inf2); } if(przod0 == tyl0 && przod1 == tyl1) cout<<"TAK\n"; else cout<<"NIE\n"; } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cerr.tie(0); cout<<setprecision(9)<<fixed; cerr<<setprecision(6)<<fixed; int test = 1; // cin>>test; while(test--){ solve(); } } /* 2 1 5 0 5 2 11 */
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 70 71 72 73 74 75 76 77 78 79 80 | //#pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; #define ll long long #define ld long double #define pi pair<int,int> #define pd pair<ld,ld> #define ft first #define sd second #define st first #define nd second #define mp make_pair #define pb push_back #define eb emplace_back #define FOR(i,a,b) for(int i=(a); i<=(b);i++) #define F(i,a,b) FOR(i,(a),(b)-1) #define REV(i,a,b) for(int i=(a); i>=(b);i--) #define VI vector<int> #define VPI vector<pi> #define VPD vector<pd> #define PI 3.14159265 #define all(x) (x).begin(), (x).end() #define sz(a) (int)((a).size()) #define int long long template<class TH> void _dbg(const char *sdbg, TH h){cerr<<sdbg<<"="<<h<<"\n";} template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) { while(*sdbg!=',')cerr<<*sdbg++;cerr<<"="<<h<<","; _dbg(sdbg+1, a...); } #define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__) const long long inf = 1000*1000*1000+7; const long long inf2 = 1000*1000*1000+9; const long long INF = LLONG_MAX; const long long MOD = inf; const long long P = 997; const long long N = 1e6+10, base=1<<19; int Mul(int _a, int _b, int _MOD=MOD){return _a*_b%_MOD;} int Pow(int _a, int _b, int _MOD=MOD){int _pom = 1;for(;_b;_b/=2,_a=Mul(_a,_a,_MOD)){if(_b&1)_pom=Mul(_pom,_a,_MOD);}return _pom;} void solve(){ int n; cin>>n; char c; int przod0=0,tyl0=0,pomP0=1; int przod1=0,tyl1=0,pomP1=1; while(cin>>c) { przod0 = (przod0 * P + c)%inf; tyl0 = (tyl0 + c * pomP0)%inf; przod1 = (przod1 * P + c)%inf2; tyl1 = (tyl1 + c * pomP1)%inf2; pomP0 = Mul(pomP0, P); pomP1 = Mul(pomP1, P,inf2); } if(przod0 == tyl0 && przod1 == tyl1) cout<<"TAK\n"; else cout<<"NIE\n"; } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cerr.tie(0); cout<<setprecision(9)<<fixed; cerr<<setprecision(6)<<fixed; int test = 1; // cin>>test; while(test--){ solve(); } } /* 2 1 5 0 5 2 11 */ |