C++ 解法, 执行用时: 11ms, 内存消耗: 508K, 提交时间: 2021-05-24 23:53:49

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#define MN 60

int n,m,t,b[MN+5],x[MN+5];

int bb[MN+5];

struct Matrix{
	int a[MN][MN];
	Matrix(int x=0){
		memset(a,0,sizeof(a));
		for(int i=0;i<n;i++)
			a[i][i] = x;
	}
	Matrix operator * (const Matrix& that)const{
		Matrix ret;
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				for(int k=0;k<n;k++){
					ret.a[i][j] ^= this->a[i][k]&that.a[k][j];
				}
			}
		}
		return ret;
	}
	Matrix operator *= (const Matrix& that){
		return *this = *this*that;
	}
};

Matrix bsc;

Matrix qpow(Matrix bsc,int y){
	Matrix ret = 1;
	while(y){
		if(y&1) ret *= bsc;
		bsc *= bsc;
		y >>= 1;
	}
	return ret;
}

void gauss(Matrix bsc){
	#define a bsc.a
	for(int i=0,s=0;i<n;i++){
		if(a[s][i]==0){
			for(int j=s+1;j<n;j++){
				if(a[j][i]==1){
					for(int k=0;k<n;k++)
						std::swap(a[s][k],a[j][k]);
					std::swap(b[s],b[j]);
					break;
				}
			}
		}
		if(a[s][i]==0) continue;
		for(int j=s+1;j<n;j++){
			if(a[j][i]==1){
				for(int k=0;k<n;k++){
					a[j][k] ^= a[s][k];
				}
				b[j] ^= b[s];
			}
		}
		s++;
	}
	for(int i=n-1;i>=0;i--){
		for(int j=0;j<n;j++){
			if(a[i][j]==1){
				for(int k=j+1;k<n;k++)
					if(a[i][k]==1){
						b[i] ^= x[k];
						a[i][k] = 0;
					}
				x[j] = b[i];
				break;
			}
		}
	}
	#undef a
}

int main(){
	scanf("%d%d%d",&n,&m,&t);
	for(int i=0;i<n;i++){
		scanf("%d",&b[i]);
		bb[i] = b[i];
	}
	for(int i=0;i<m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		--u,--v;
		bsc.a[u][v] = bsc.a[v][u] = 1;
	}
	for(int i=0;i<n;i++)
		bsc.a[i][i] = 1;
	bsc = qpow(bsc,t);
	gauss(bsc);
	for(int i=0;i<n;i++){
		int ans = 0;
		for(int j=0;j<n;j++){
			if(bsc.a[i][j]) ans ^= x[j];
		}
		if(ans!=bb[i]){
			printf("Error on node %d : expect %d, get %d\n",i,bb[i],ans);
			exit(1);
		}
	}
	for(int i=0;i<n;i++)
		printf("%d%c",x[i]," \n"[i==n-1]);
}