BOJ 3997 - 하이퍼드롬
홀수, 짝수 팰린드롬을 따로 생각해준다.
짝수가 되려면 번째에서 자신의 왼쪽으로 번째 알파벳이 짝수면 , 홀수면 이 되는 parity 들의 집합을 구간합 배열로 카운팅해둔다.
그럼 현재 까지의 parity를 라고 하면 이전까지의 구간합 배열의 값 중 와 일치하는 것이 있으면 그 구간은 하나의 팰린드롬이라고 볼 수 있다.
짝수라면 개의 알파벳이 개이고 나머지는 모두 인 것의 개수를 세주면 된다.
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;
}
Comments