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
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include <iostream>
#include <vector>
using namespace std;

#define WORD unsigned short int
//#define CWIERC 5000052
#define CWIERC 4100001
#define KOD_A (char)97
#define SYMBOLI 26
#define PIERWSZA1 1001411
#define PIERWSZA2 1007519

vector<WORD> bufor(CWIERC / 3);

void ZapiszZnak(int ind, char znak) {
  int komorka = ((ind % CWIERC) / 3);
  int slot = ((ind % CWIERC) % 3);
  switch(slot) {
    case 0:
      bufor[komorka] = (bufor[komorka] & (WORD)0b1111111111100000) + ((WORD)(znak));
      break;
    case 1:
      bufor[komorka] = (bufor[komorka] & (WORD)0b1111110000011111) + ((WORD)(znak) << 5);
      break;
    case 2:
      bufor[komorka] = (bufor[komorka] & (WORD)0b1000001111111111) + ((WORD)(znak) << 10);
      break;
  }
}

char OdczytajZnak(int ind) {
  int komorka = ((ind % CWIERC) / 3);
  int slot = ((ind % CWIERC) % 3);
  switch(slot) {
    case 0:
      return ((bufor[komorka] & (WORD)0b0000000000011111));
      break;
    case 1:
      return ((bufor[komorka] & (WORD)0b0000001111100000) >> 5);
      break;
    case 2:
      return ((bufor[komorka] & (WORD)0b0111110000000000) >> 10);
      break;
  }
  return 'X';
}

long long power_modulo_fast(long a, long b, long m) {
  long i;
  long long wynik = 1;
  long long x = a % m;

  for (i = 1; i <= b; i <<= 1) {
    x %= m;
    if((b & i) != 0) {
      wynik *= x;
      wynik %= m;
    }
    x *= x;
  }
  return wynik % m;
}

int main() {
  ios_base::sync_with_stdio(0);
  long n;
  char litera;
  long licznik = 1;
  long long hl1 = 0, hp1 = 0, hl2 = 0, hp2 = 0;
  long long powHl1 = 1, powHl2 = 1, powHp1 = 1, powHp2 = 1;

  cin >> n;
  if(n == 1) {
    cout << "TAK";
    return 0;
  }
  
  if(n) {
    cin >> litera;
    litera -= KOD_A;
    hl1 = ((hl1 * SYMBOLI) + litera) % PIERWSZA1;
    hl2 = ((hl2 * SYMBOLI) + litera) % PIERWSZA2;
    
    for(long i = 1; i < (n + 1) / 2; ++i) {
      cin >> litera;
      litera -= KOD_A;

      powHl1 = (powHl1 * SYMBOLI) % PIERWSZA1;
      powHl2 = (powHl2 * SYMBOLI) % PIERWSZA2;
      
      hl1 = (hl1 + powHl1 * litera) % PIERWSZA1;
      hl2 = (hl2 + powHl2 * litera) % PIERWSZA2;
    }
    
    if(n % 2) {
      hp1 = ((hp1 * SYMBOLI) + litera) % PIERWSZA1;
      hp2 = ((hp2 * SYMBOLI) + litera) % PIERWSZA2;
    }
    
    while(cin >> litera) {
      litera -= KOD_A;
      hp1 = ((hp1 * SYMBOLI) + litera) % PIERWSZA1;
      hp2 = ((hp2 * SYMBOLI) + litera) % PIERWSZA2;
    }
    
    if((hl1 == hp1) && (hl2 == hp2))
      cout << "TAK";
    else
      cout << "NIE";
    return 0;
  }

  cin >> litera;
  litera -= KOD_A;
  ZapiszZnak(licznik, litera);

  hl1 = ((hl1 * SYMBOLI) + litera) % PIERWSZA1; hp1 = hl1;
  hl2 = ((hl2 * SYMBOLI) + litera) % PIERWSZA2; hp2 = hl2;
  while(cin >> litera) {
    ++licznik;
    litera -= KOD_A;
    if(licznik <= 8200000L)
      ZapiszZnak(licznik, litera);
    if(licznik % 2) {
      //Odwrocony Rabin Karp
      powHl1 = (powHl1 * SYMBOLI) % PIERWSZA1;
      powHl2 = (powHl2 * SYMBOLI) % PIERWSZA2;
      
      hl1 = (hl1 + powHl1 * OdczytajZnak((licznik + 1) / 2)) % PIERWSZA1;
      hl2 = (hl2 + powHl2 * OdczytajZnak((licznik + 1) / 2)) % PIERWSZA2;

      hp1 = ((hp1 * SYMBOLI) + litera) % PIERWSZA1;
      hp2 = ((hp2 * SYMBOLI) + litera) % PIERWSZA2;
    } else {
      if(licznik > 2) {
        powHp1 = (powHp1 * SYMBOLI) % PIERWSZA1;
        powHp2 = (powHp2 * SYMBOLI) % PIERWSZA2;
      }

      hp1 = ((hp1 - powHp1 * OdczytajZnak(licznik / 2)) * SYMBOLI + litera) % PIERWSZA1;
      if(hp1 < 0)
        hp1 += PIERWSZA1;
      hp2 = ((hp2 - powHp2 * OdczytajZnak(licznik / 2)) * SYMBOLI + litera) % PIERWSZA2;
      if(hp2 < 0)
        hp2 += PIERWSZA2;
    }
  }
  if((hl1 == hp1) && (hl2 == hp2))
    cout << "TAK";
  else
    cout << "NIE";
  //cout << endl << hl1 << " - " << hp1 << " - " << hl2 << " - " << hp2;
  return 0;
}