C++14(g++5.4) 解法, 执行用时: 1076ms, 内存消耗: 4572K, 提交时间: 2019-08-13 15:36:37

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int const maxn=1<<20,mod=1e9+7;
int a[10],f[maxn],n,m,k;
void fwt(int num){
    for(int k=1;k<num;k<<=1) for(int i=0;i<num;i+=(k<<1))
    for(int j=0;j<k;j++) {
        int x=f[i+j],y=f[i+j+k];
        f[i+j]=x+y;
        f[i+j+k]=x-y;
    }
}
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);
        }
        fwt(1<<k);
        ll res=0,cnt=1;
        for(int i=0;i<1<<k;i++){
            res^=cnt*(f[i]>>m)%mod;
            cnt=cnt*3%mod;
        }
        printf("%lld\n",res);
    }
}

C++ 解法, 执行用时: 641ms, 内存消耗: 4372K, 提交时间: 2022-06-18 19:39:26

#include <bits/stdc++.h>
using namespace std;
const long long MOD=1e9+7;
const int maxn=1<<20;
int n,m,k;
int f[maxn],a[maxn];
void fwt(int a[],int n){
	for(int d=1;d<n;d<<=1){
		for(int m=d<<1,i=0;i<n;i+=m){
			for(int j=0;j<d;j++){
				int x=a[i+j],y=a[i+j+d];
				a[i+j]=(x+y);
				a[i+j+d]=(x-y);
			}
		}
	}
}
void dfs(int x,int re,int p)
{
	if(x==m)
	{
		f[re]+=p;
		return ;
	}
	dfs(x+1,re,p);
	dfs(x+1,re^a[x],-p);
}
int main()
{
	while(~scanf("%d%d%d",&n,&m,&k))
	{
		for(int i=0;i<1<<k;i++)f[i]=0;
		for(int i=1;i<=n;i++)
		{
			for(int j=0;j<m;j++)
			{
				scanf("%lld",&a[j]) ;
			}
			dfs(0,0,1);
		}
		fwt(f,1<<k);
		long long ans=0,tmp=1;
		for(int i=0;i<1<<k;i++)
		{
			ans^=(f[i]>>m)*tmp%MOD;
			tmp=tmp*3%MOD;
		}
		printf("%lld\n",ans);
	}
}