백준 3997 하이퍼드롬

https://www.acmicpc.net/problem/3997

DP 문제인 줄 알고 헤맸었는데, 아이디어성 문제입니다.

  1. 문자의 개수가 총 52개이기 때문에 [1,x] 구간에서 문자가 출현한 횟수의 홀짝성을 long long 정수에 저장할 수 있습니다. (52개 알파벳을 [0,52) 에 매칭한 후, 해당 자리수의 비트를 홀수일때 1, 짝수일때 0로 합니다.)

  2. [i,j] 구간에서의 홀짝성은 [1,j] xor [1,i-1]과 같습니다. 이때 하이퍼드롬이 되려면 [i,j] 구간에서 홀수의 개수는 0또는 1이여야만 합니다. 따라서 [1,i-1]의 홀짝성은 [1,j] xor 0 , 또는 [1,j] xor (1«k) ($ 0 \leq k < 52 $) 인 53가지 경우만 가능합니다.

map에 지금까지 나왔던 홀짝성들(long long 정수)을 모두 저장해두고 찾으면 O(53nlog(n)) 시간복잡도로 풀 수 있겠네요.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int ALPHA=26;
map<ll,ll> vst;
int main(void){
	ios::sync_with_stdio(false); cin.tie(NULL);
	int n; cin>>n;
	string s; cin>>s;
	ll x=0LL,ans=0LL;
	vst[0]=1LL;
	for(int i=0;i<n;i++){
		int a=(islower(s[i])?s[i]-'a':s[i]-'A'+ALPHA);
		x^=(1LL<<a);
		ans+=vst[x];
		for(int j=0;j<2*26;j++){
			if(vst.find(x^(1LL<<j))!=vst.end()) ans+=vst[x^(1LL<<j)];
		}
		vst[x]++;
	}
	cout<<ans;
	return 0;
}