题目大意：有n个m元组\(v_1, v_2, \cdots, v_n\)，第i个m元组\(v_i = a_{i,1}, a_{i,2}, \cdots , a_{i,m}\)。定义\(count(x)\)为这n个m元组中，对所有\(j = 1 \cdots m\)满足\(a_{i,j} \oplus x\)的二进制表示中有奇数个1的m元组的个数。求\(count(x), x = 0 \cdots 2^k – 1\)，其中\(1 \leq n \leq 10^5\)，\(0 \leq a_{i,j} < 2^k\)，\(1 \leq k \leq 20\)，\(1 \leq m \leq 10\)。 题解：观察FWHT中的Haramard矩阵，\(H_{ij}=(-1)^{count1(i\ and\ j)}\)，其中\(count1(x)\)表示x的二进制表示中1的数量；这和我们题目中要的东西很像。关于这道题目，我们可以发现我们并不需要做什么卷积；也就是说，我们其实并没有在做一个完整的FWHT。做这道题主要用到的是FWHT中的那个Haramard变换矩阵，然后我们有方法在和这个矩阵做矩阵乘法的时候把时间复杂度降到\(O(n\log (n))\)，所以做这道题只需要知道\(H_{ij}=(-1)^{count1(i\ and\ j)}\)，然后贴个FWHT的板子使做该矩阵乘法的时间复杂度降到\(O(n\log (n))\)就好了（完全不知道WHT是啥的也可以先看一下http://www.zarxdy34.top/?p=203来帮我增加一下访问量）。 为了方便起见，设\(f(x)=(-1)^{count1(x)}\)，即x二进制表示下有奇数个1时为-1,偶数个1时为1，\(H_{ij}=f(i \oplus j)\)。由于有如下性质： \[ \begin{aligned} H_{t(x \oplus y)} &=(-1)^{count1(t\…