bitset的优化暴力

最近做题遇到了一道bitset才能解决的暴力优化方案，题目本身挺有趣的，感觉可以写一下。
题目链接

题意

题目非常简单明了，就是规定两行(a, b)，如果两行中对应列的$a_i = b_i$，就算贡献 + 1，如果最后贡献为奇数，那么答案+1，求最后的答案是多少。

做法

首先明确$N$的范围是$10^3$
(不管怎么样，先暴力再说)
最暴力的方法当然外层枚举这两行，内层判断其对应位置相同元素的个数是否为奇数。
不过这么做的复杂度就是$O(N^3)$，怎么说都会爆炸吧

优化

对于一个$O(n)$的内循环，可以通过bitset来优化为$O(\frac{n}{w})$，其中w为计算机字节长度。
这样就可以直接卡过去了。
其实让我最感兴趣的是这个计算答案的方式，这是值得分析的：
在使用bitset优化的过程中，我们改变了枚举的顺序：最外层枚举是每一列的每个数，第二层枚举才是每一行
对于这一列，我们可以按照$A_j$来分组，所有$A_j$相等的行为一组，对于每一组，我们有以下分析：
假设$a, b, c$三行为一组，如果此前明没有过相等的元素，那么(a, b), (a, c), (b, c)将成为三个贡献为1的数对，但如果此前的某一列$a, b$有1个相等的元素，那么(a, b)就有偶数个相等的数，不算贡献。
既然答贡献只与奇偶性有关系，那么异或这个两次相同操作可以抵消的性质就非常适合我们选择。（$a\;xor\;b\;xor\;b\;=\;a$）
对于每一组，我们使用bitset中的1所对应的位置来表示组内行号，构成变量tmp
再将答案ans[i] ^= tmp（i为组内行号）
经过所有列的枚举，最终的ans[i]中1的个数就是与i有奇数个相等元素的行数
通过累加、去除重复之后即可得到最后答案。