「NOIOL #3」魔法值

题意：一个 $n$ 个点 $m$ 条边的图，第 $j$ 天城市 $i$ 的魔法值为 $f_{i,j}$，第 $0$ 天的魔法值为 $f_{i,0}$，魔法值的计算公式如下：

$$f_{x,j}=f_{v_1,j-1}\oplus f_{v_2,j-1}\oplus \cdots\oplus f_{v_k,j-1}$$

其中 $j\ge 1$，$v _1,v _2,\cdots,v _k$ 是所有直接与 $x$ 号称是直接相连的城市，$\oplus$ 为异或运算。

现在有 $q$ 个问题，每个问题问你第 $a$ 天时 $1$ 号城市的魔法值。

解析：

一道矩阵乘法的题。。。

首先观察题目容易发现每天的魔法值由前一天得到，即存在递推关系，可以写出递推式：

$$f _{v,j}=\text{xor} _{u=1} ^{n} f _{u,j-1}\times e _{u,v}$$

其中 $e _{u,v}$ 代表 $(u,v)$ 之间是否有边，有则为 $1$，否则为 $0$。

容易发现这是一个矩阵乘法的标准式子，我们可以直接求出 $e$ 矩阵的幂与 $f _{0}$ 相乘即可得到答案。

由于要多次询问，为了避免时间超限，我们预处理出 $e ^1,e ^2,e ^4,\cdots,e ^{2147483648}$，最后答案二进制拆分依次相乘即可。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<ctime>
#define INF 1e9
using namespace std;
const int maxn=110;
const double Pi=acos(-1.0);
template<class T>void read(T &x)
{
	x=0;int f=0;char ch=getchar();
	while(ch<'0'||ch>'9') {f|=(ch=='-');ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	x=f?-x:x;
	return;
}
int n,m,q;
long long f[maxn],x[maxn],num[maxn];
struct matrix
{
	bool a[maxn][maxn];
	matrix()
	{
		memset(a,0,sizeof(a));
	}
}p[41];
matrix multi(matrix u,matrix v)
{
	matrix w;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			for(int k=1;k<=n;k++)
				w.a[i][j]^=(u.a[i][k]&v.a[k][j]);
	return w;
}
void power(long long u)
{
	memset(num,0,sizeof(num));
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(p[u].a[i][j])
				num[i]=num[i]^x[j];
	for(int i=1;i<=n;i++)
		x[i]=num[i];
}
int main()
{
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;i++)
		scanf("%lld",&f[i]);
	for(int i=1;i<=m;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		p[0].a[u][v]=p[0].a[v][u]=1;
	}
	for(int i=1;i<=31;i++)
		p[i]=multi(p[i-1],p[i-1]);//预处理边矩阵的所有2次幂
	for(int i=1;i<=q;i++)
	{
		for(int j=1;j<=n;j++)
			x[j]=f[j];//初始化
		long long y;
		scanf("%lld",&y);
		for(int j=0;j<=31;j++)
			if(y&(1ll<<j))
				power(j);//二进制拆分
		printf("%lld\n",x[1]);
	}
	return 0;
}