※ 引述 《Rushia (早瀬ユウカの体操服)》 之铭言：
:
: https://leetcode.com/problems/number-of-wonderful-substrings/description
: 1915. Number of Wonderful Substrings
: 给你一个包含小写字母a~j的字串，如果一个子字串的所有字母只有一个字母出现奇数次
: 那么他就是一个超赞字串，求出s里面有几个超赞子字串。
:
: 思路：
: 1.我们要判断一个字串是不是超赞字串要检查他的奇偶，我们可以用一个二进制数字表
: 示，奇数为1偶数为0，因为有10个 字母所以需要10位数的二进制就可以表示，状
: 态初始化为0000000000 -> i = -1 (什么都不加必定是偶数)
: 假设加入一个a状态变成1000000000 -> i = 0
: 加入一个b状态变成1100000000 -> i = 1
: 加入一个a状态变成0100000000 -> i = 2
: 加入一个b状态变成0000000000 -> i = 3
: ...
: 为了方便讨论，后面我们称二进制数字为"状态"
:
: 2.如果 i 不同但是状态相同(例如上面i=-1和i=3)，两个"状态"之间的字母必定只会出
: 现偶数次(奇数不可能相同)，所以：
: b ... [xxxxx] ... b
:
: 如果最后一个b的状态等于前面的那个b，可以不断地扩展会变成：
:
: b -> [中间必定是偶数] -> b -> [中间必定是偶数] -> b
:
: 因为这个特性，只要当前的状态前面出现过，他就可以跟前面的状态接在一起变成一
: 个新的超赞数字，就像是
: b => bb => bbb
: 这样所以我们只要找有几个b就好，找的过程又可以分成奇偶两个case。
:
: 3.可以使用前缀和技巧求解，因为最多有2^10个状态所以可以把map换成array
: 假定 cnt[x] 表示二进制x这个状态的出现次数:
: (1) 任何数加上偶数，奇偶性不变。
: 同第二点所述，累加前面的 cnt[x] 总数(只要该状态有出现过就一定可以累加)
: (2) 任何数加上奇数，奇数变偶数，偶数变奇数。
: 假设前面存在一个前缀字串 x 可和 word[i] 组成一个超赞字串，那么必定满足:
: x ^ word[i] = 只有一个一的二进制数
: 而该数x刚好会等于 word[i] 的状态每个位数翻转1，假定 word[i]=0000000010
: 0000000011 ^ 0000000010 = 0000000001
: 0000000000 ^ 0000000010 = 0000000010
: 0000000110 ^ 0000000010 = 0000000100
: 0000001010 ^ 0000000010 = 0000001000
: 0000010010 ^ 0000000010 = 0000010000
: 0000100010 ^ 0000000010 = 0000100000
: 0001000010 ^ 0000000010 = 0001000000
: 0010000010 ^ 0000000010 = 0010000000
: 0100000010 ^ 0000000010 = 0100000000
: 1000000010 ^ 0000000010 = 1000000000
: 所以我们去找前面所有 word[i] 翻转一个位元的状态共有几个，全部累加起来就好。
思路:
哇靠 这三小
这是dp吗?
(30分钟之后)
干拎娘 谁他妈给这标成medium 的
摧毁别人自尊很好玩是不是
怎么不去给狗干
对不起对不起对不起对不起对不起对不起
然后我跑去留言区看提示
bitset
prefix sum
好 我试试看 结果成功 好爽
https://i.imgur.com/oBstnsI.jpeg
先把他弄成只有四个字母的bitset试试看
为什么只有0跟1?
因为有几个根本不重要
重点是他字串开头到结尾有几个奇数的
开始进入word
然后先看第一个字
改变当时bitset 并且记录
同时去前面看有没有能接的bitset
然后再继续干到最后
怎么看有没有能接的bitset?
他进来的时候 如果要只有一个以下是奇数
那这样 代表
1: 他就都没有
2: 他有一个
然后往回找要找什么?
1: 要找的是最多一个奇数的
2: 要找的就是可以跟他弄成刚好没有奇数的
所以往回找时
要看两个情况
1: 刚好跟他差一个bit的
也就是说他们之间刚好多一个或是少一个奇数
2: 找到跟他bitset长一样
就是一样的
这样他们两个之间就一定是都是偶数
然后1跟2都可以直接加上
在那个位子出现的子字串
也就是那一种bitset的数量
```cpp
class Solution {
public:
long long wonderfulSubstrings(string word) {
long long res = 0;
int len = word.size();
bitset<10> now;
bitset<10> nowone;
unordered_map<bitset<10>,long long> paper;
paper[now]++;
for(int i = 0 ; i < len ; i ++)
{
now[word[i]-'a'] = now[word[i]-'a'] ^ 1;
for(int j = 0 ; j < 10 ; j ++)
{
nowone = now;
nowone[j] = nowone[j] ^ 1;
res += paper[nowone];
}
res += paper[now];
paper[now] ++;
}
return res;
}
};
```