BOJ 3997 - 하이퍼드롬

BOJ 3997 - 하이퍼드롬

홀수, 짝수 팰린드롬을 따로 생각해준다.

짝수가 되려면 $i$번째에서 자신의 왼쪽으로 $j$ 번째 알파벳이 짝수면 $2^j=0$, 홀수면 $2^j=1$ 이 되는 parity 들의 집합을 구간합 배열로 카운팅해둔다.

그럼 현재 $0 \to i$ 까지의 parity를 $K$라고 하면 이전까지의 구간합 배열의 값 중 $K$ 와 일치하는 것이 있으면 그 구간은 하나의 팰린드롬이라고 볼 수 있다.

짝수라면 $26$개의 알파벳이 $1$개이고 나머지는 모두 $0$인 것의 개수를 세주면 된다.

int idx(char c) {
   if (c >= 'a' && c <= 'z') return c - 'a';
   return c - 'A' + 26;
}
void solve() {
   map<int, int> cnt;
   int n;
   cin >> n;
   string s;
   cin >> s;
   cnt[0]++;
   int bit = 0;
   int ans = 0;
   for (int i = 0; i < n; i++) {
      bit ^= (1ll << idx(s[i]));
      ans += cnt[bit];
      cnt[bit]++;
   }
   bit = 0;
   cnt.clear();
   cnt[0]++;
   for (int i = 0; i < n; i++) {
      bit ^= (1ll << idx(s[i]));
      // center char
      for (int j = 0; j < 52; j++) {
         int t = bit ^ (1ll << j);
         if (hass(cnt, t))
            ans += cnt[t];
      }
      cnt[bit]++;
   }
   cout << ans;
}