题目大意：有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\le n\le {10}^5$，$0\le a_{i,j}<2^k$，$1\le k\le 20$，$1\le m\le 10$。

题解：观察FWHT中的Haramard矩阵，$H_{ij}=(-1{)}^{count1(iandj)}$，其中$count1(x)$表示x的二进制表示中1的数量；这和我们题目中要的东西很像。关于这道题目，我们可以发现我们并不需要做什么卷积；也就是说，我们其实并没有在做一个完整的FWHT。做这道题主要用到的是FWHT中的那个Haramard变换矩阵，然后我们有方法在和这个矩阵做矩阵乘法的时候把时间复杂度降到$O(n\log (n))$，所以做这道题只需要知道$H_{ij}=(-1{)}^{count1(iandj)}$，然后贴个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{array}{rl}{H}_{t(x\oplus y)}& =(-1{)}^{count1(tand(x\oplus y))}\\ & =(-1{)}^{count1((tandx)\oplus (tandy))–2k}\\ & =(-1{)}^{count1((tandx)\oplus (tandy))}\\ & =H_{tx}\cdot H_{ty}\end{array}$$

所以有$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$，我们想要让$[x^t]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。要让该式子对$[x^t]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);
	}
}