my 9.15 T3
子串的好串
涉及到的几个点实在值得记录一下：
1. 状压+hash
2. 前缀次数统计
3. 强制添加字符+前缀，以反向求仅有一个字符的子串，前缀次数统计可以考虑完所有的子串情况
func main() {
var s string
fmt.Scanln(&s)
m := make(map[int]int)
cur := 0
ans := 0
m[0] = 1
for i := 0; i < len(s); i++ {
// 状压，所有奇数个字符的情况都压缩到了一个数中，作为前缀
cur ^= 1 << int(s[i]-'a')
// 强制添加一次每个字符(cur^(1<<i))，如果之前有过前缀，那么前缀的结尾到当前位置这个添加的字符数就是奇数，其他字符都是偶数
for i := 0; i < 26; i++ {
ans += m[cur^(1<<i)]
}
// 因为前缀之前可能出现过
m[cur] = m[cur] + 1
}
fmt.Println(ans)
} 
投递百度等公司10个岗位 >
