前缀和的二进制处理

题目链接
题目大意：
如果某个字符串中 至多一个 字母出现 奇数 次，则称其为 最美 字符串。

例如，"ccjjc" 和 "abab" 都是最美字符串，但 "ab" 不是。
给你一个字符串 word ，该字符串由前十个小写英文字母组成（'a' 到 'j'）。请你返回 word 中 最美非空子字符串 的数目。如果同样的子字符串在 word 中出现多次，那么应当对 每次出现 分别计数。

子字符串 是字符串中的一个连续字符序列。
示例 1：
输入：word = "aba"
输出：4
解释：4 个最美子字符串如下所示：

• "aba" -> "a"
• "aba" -> "b"
• "aba" -> "a"
• "aba" -> "aba"
  解题思路：
  用到了很常见前缀和二进制处理技巧（遇到很多次还是不会，--呜呜呜）。
  因为只有a~j十个数字，所以我们可以用十位二进制来表示一个字符串的状态，0表示这个字母出现的次数为偶数，1表示出现仅次数为奇数。如果一段i-j字符串各个数字的奇偶性相同，那么前缀和i-1和前缀和j相同。题目要求可以有一个数字出现奇数次，我们只需要枚举每个位数，将这个位数反转过来，如果之前的前缀和存在这个数，那么加上反转过的数的个数。

  class Solution {
  public:
    long long wonderfulSubstrings(string word) {
        int p[1024];
        for(int i=0;i<1024;i++) p[i]=0;//初始化为0
        p[0]=1;//所有出现的字母都为偶数+1
        int pre=0;
        long long ans=0;
        int len=word.length();
        for(int i=0;i<len;i++){
            pre=pre^(1<<(word[i]-'a'));//处理前缀和，如果前i-1的x字母为奇数，1&1=0变为偶数，反之如果前i-1的x字母为偶数，0&1=1变为奇数；
            ans+=p[pre];//如果之前出现过相同的数字，加上之前这个数的个数
            for(int j=1;j<1024;j<<=1){//枚举二级制的每一位，将其反转过来，就满足出现一个数字个个数为奇数的情况，加上它的个数。
                ans+=p[pre^j];
            }
            p[pre]++;
        }
        return ans;
    }
  };

• 总之异或运算是个处理奇偶关系的好东西（主要还是要熟悉二进制运算），善于用二进制解决问题可以是算法效率大大提高，代码也会很好看。*