题目大意:有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);
	}
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注