intn;vsword;vviis_odd;structtrie{intcnt=0,depth;trie*t_odd=0,*t_even=0,*t_zero=0;trie(intdepth,intyes_cnt=0):depth(depth){}voidadd(inti){if(depth==26){cnt++;return;}intodd=is_odd[i][depth]%2==1;inteven=!odd&&is_odd[i][depth]>0;intzero=is_odd[i][depth]==0;if(odd){if(!t_odd)t_odd=newtrie(depth+1);t_odd->add(i);}elseif(even){if(!t_even)t_even=newtrie(depth+1);t_even->add(i);}else{if(!t_zero)t_zero=newtrie(depth+1);t_zero->add(i);}}intquery(inti,intno_depth){if(depth==26){returncnt;}intodd=is_odd[i][depth]%2==1;inteven=!odd&&is_odd[i][depth]>0;intzero=is_odd[i][depth]==0;if(odd^even^zero!=1){debug(i,depth,odd,even,zero);}assert(odd^even^zero==1);if(depth==no_depth){if(!t_zero)return0;returnt_zero->query(i,no_depth);}elseif(zero){if(!t_odd)return0;returnt_odd->query(i,no_depth);}else{if(odd){// zero나 evenintret=0;if(t_even)ret+=t_even->query(i,no_depth);if(t_zero)ret+=t_zero->query(i,no_depth);returnret;}else{if(!t_odd)return0;returnt_odd->query(i,no_depth);}}}};voidsolve(){cin>>n;word.resize(n);fv(word);is_odd=vvi(n,vi(26));for(inti=0;i<n;i++){for(charc:word[i]){is_odd[i][c-'a']++;}}trie*root=newtrie(0);for(inti=0;i<n;i++){if(sz(word[i])%2==1){root->add(i);}}debug(is_odd);llans=0;for(inti=0;i<n;i++){if(sz(word[i])%2==0){// 모든 알파벳을 다쓴 문자열이면 불가능// 안 쓴 알파벳중 제외할 것 하나만 고르고 나머지를 모두 가지게 해보자.// 쓴거라면 항상 even, odd를 결정할 수 있고// 안쓸 것이라면 항상 odd만 고르고// 안쓴 것인데 써야한다면 odd 를 고른다.for(intj=0;j<26;j++){if(is_odd[i][j]==0){ans+=root->query(i,j);}}}}cout<<ans;}
에디토리얼 풀이
생각을 해보면 이상하게 홀수가 있어야 된다는 조건이 많은것이 결국 $\oplus$해서 $1$ 인 것을 의미하는 것이였는데 생각을 못한것이 아쉽다.
$f(x)$가 $x$의 비트 수라고 한다면,
$f(a_i \vert a_j)=f(a_i \oplus a_j)=25$ 여야 한다는 것이 조건이다.
어떤 $a_i$에 대해 $26$개의 문자 중 쓰이지 않은 것들 중에 최종 문자열에도 안 쓰일 것을 정하면
Comments