[AtCoder] CODE FESTIVAL 2017 qual C D: Yet Another Palindrome Partitioning

題目連結:http://code-festival-2017-qualc.contest.atcoder.jp/tasks/code_festival_2017_qualc_d

---

賽中唬爛了一個爛DP，很正常的TLE掉，賽後看著Editorial還是看不懂，只好去問別人QQ。
我用editorial的方式講一下好了：我們定義一種hash值$h(\text{str})=\sum_{i=0}^{26}2^i \cdot (sum(i) \mod 2)$其中$sum(i)$代表字元$i$出現幾次。這樣的話，我們會發現如果$\text{str}$是回文，若且唯若$h(\text{str})$是二的冪次或零(因為出現次數為奇的最多只能有一個)，接下來我們幫$\text{str}$的前綴算好hash值($h_i$代表$[0, i)$的hash值)，而另外一個小發現則是發現要算$\text{str}$中$[l, r)$的hash值，我們只要計算$h_l \oplus h_r$就好了。
那現在我們可以開始DP了，我們狀態是$dp[i]$代表$[0, i]$中我們至少要切幾段才能使得每塊都可以變回文，那我們會發現其實就是要找到最小的$dp[j]$使得$h_j \oplus h_i$是二的冪次或零，那這時我們再DP另外一個數字$val[S]$代表當$a_i=S$的最小$dp[i]$值，而因為xor的特性，我們只要枚舉$val[a_i], val[a_i \oplus 2^0], val[a_i \oplus 2^1] \cdots val[a_i \oplus 2^25]$就可以得到答案了(因為$(A \oplus B) \oplus A = B$)，而得到答案後記得再更新一下$val[a_i]$即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 200000 + 5;
const int INF = 1<<30;
 
string ss;
int dp[1<<26], ans[N];
 
int main(){
	cin>>ss;
	int n = ss.size(), cur = 0;
	fill(dp, dp+(1<<26), INF);
	dp[cur] = 0;
	for(int i=0;i<n;i++){
		cur ^= (1<<(ss[i]-'a'));
		ans[i] = dp[cur]+1;
		for(int j=0;j<26;j++) ans[i] = min(ans[i], dp[cur ^ (1<<j)]+1);
		dp[cur] = min(dp[cur], ans[i]);
	}
	cout<<ans[n-1]<<'\n';
	return 0;
}