HDU 4909 String 計數：狀態壓縮與分段枚舉另版實現

HDU 4909 String 計數：狀態壓縮與分段枚舉另版實現

同 HDU 4909，本文提供另一份代碼，使用 sort + 雙指針統計相等對，並對 ? 位置枚舉 26 字母及空情況。

代碼亮點

• 無 ? 時：前綴異或陣列 s[] 排序，統計相同值組合數 C(cnt,2)。
• 有 ? 時：
  　① 分三段：左段、右段、跨越段。
  　② 右段狀態預先異或各字母掩碼。
  　③ handle 函數雙指針合併左段排序狀態與右段修正狀態。
  　④ solve() 復用無 ? 邏輯。

關鍵函數

ll solve() { // 無 ? 或視 ? 為普通字符
    int tmp = 0; s[0]=0;
    for (int i=1; i<=n; i++) if (str[i]!='?') tmp ^= 1<<(str[i]-'a'), s[i]=tmp;
    sort(s, s+n+1);
    ll ret=0;
    for (int i=0, j; i<=n; i=j) {
        for (j=i; j<=n && s[j]==s[i]; j++);
        ret += (ll)(j-i)*(j-i-1)/2;
    }
    return ret;
}

ll handle(int x, int pos) { // ? 替換字母 x
    // 左段 a[0..pos-1] = s[0..pos-1]
    // 右段 b[0..n-pos] = s[pos..n] ^ (1<

優化細節

用靜態數組 a[], b[] 避免重複分配。
sort 後雙指針 O(n) 合併，總體 26 * O(n log n)。
C++ 編譯可能卡常，G++ 通過（作者提到）。


兩版本算法一致，代碼組織略有不同，均屬標準解法。