题目大意：有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\ and (x \oplus y))} \\
&= (-1)^{count1((t\ and\ x) \oplus (t\ and\ y)) – 2k} \\
&= (-1)^{count1((t\ and\ x) \oplus (t\ and\ y))} \\
&= H_{tx} \cdot H_{ty} \end{aligned} \]
所以有\(f(x \oplus y) = f(x) \cdot f(y)\)。
设向量\(X=(X_0,X_1,\cdots,X_{2^k-1})\)，考虑\(Y=H \cdot X\)，有
\[Y_i = \sum_{j=0}^{2^k-1}{H_{ij} \cdot X_j}\]
即如果\(f(i \oplus j)=1\)，则向量\(X\)对\(Y_i\)的贡献加上\(X_j\)，否则减去\(X_j\)。
现在固定x=t，考虑每一个m元组的生成函数\(F_i\)，我们想要让\( \lbrack x^t \rbrack WHT(F_i) = 1\)（也就是\(H \cdot F_i\)所得向量的第t项）当且仅当对所有\(j = 1 \cdots m\)有\(f(a_{i,j} \oplus u) = -1\)，即如果有一个\(count1(a_{i,j} \oplus u)\)为偶数则贡献为0。要让该式子对\( \lbrack x^t \rbrack WHT(F_i)\) 贡献为1很难做到（其实也不难，就是下面那个东西除以\(2^m\)），但是我们只要做到让它的贡献为与\(a_{i,j}\)无关的一个定值就可以了。设\(b_j=-f(a_{i,j} \oplus u)\)，构造式子
\[(1+b_1) \cdot (1+b_2) \cdot (1+b_3) \cdot \cdots \cdot (1+b_m)\]
只要其中出现了一次\(b_j=-1\)，即某个\(a_{i,j} \oplus u\)中1的个数为偶数时，该式的值即为0；否则，该式值恒为\(2^m\)。
对于式子中的\(b_j\)，我们对该式的生成函数\(F_i += (-1) \cdot x^{a_j}\)，对应位置上就加上了\(b_j\)的贡献。但式子展开后还有一个常数项以及若干个\(b_{jk}\)的乘积，至于\(b_{j1} \cdot b_{j2}\)之类的项，由于有如下性质：
所以可以发现，\(b_{j1} \cdot b_{j2}\)对应的项是\(x^{a_{i,j1} \oplus a_{i,j2}}\)，系数就是它们的乘积，（单个为-1，所以两个异或起来的就是1，三个则是-1，依次类推），常数项对应一个都不取的情况。
由于FWHT是一个线性运算，所以可以把每个m元组，甚至每个m元组中的每一项的贡献单独计算并相加，所以就可以直接先把所有项全部加起来然后直接做一次FWHT得出答案。
#include <bits/stdc++.h>
using namespace std;
const int maxn=1<<20,mo=1e9+7;
void FWHT(int *arr,int N,int inv_flg=0)
{
for (int k=1;k<N;k<<=1)
for (int i=0;i<N;i+=(k<<1))
for (int j=0;j<k;j++)
{
if (inv_flg)
{
int x=arr[i+j],y=arr[i+j+k];
arr[i+j]=(x+y)/2;
arr[i+j+k]=(x-y)/2;
}
else
{
int x=arr[i+j],y=arr[i+j+k];
arr[i+j]=x+y;
arr[i+j+k]=x-y;
}
}
}
int f[maxn];
int a[11];
int n,m,k,N;
void DFS(int x,int res,int p)
{
if (x==m)
{
f[res]+=p;
return;
}
DFS(x+1,res,p);
DFS(x+1,res^a[x],-p);
}
int main()
{
while (scanf("%d%d%d",&n,&m,&k)!=EOF)
{
for (int i=0;i<(1<<k);i++) f[i]=0;
for (int i=0;i<n;i++)
{
for (int j=0;j<m;j++) scanf("%d",&a[j]);
DFS(0,0,1);
}
FWHT(f,1<<k);
int res=0;
for (int i=0,p=1;i<(1<<k);i++,p=p*3ll%mo)
res^=(long long)p*(f[i]>>m)%mo;
printf("%d\n",res);
}
}