前言
好题，考的时候用循环节做法水了部分分。看上去是图论实际上是矩阵乘(yi)法(huo)。
题面
H 国的交通由 $n$ 座城市与 $m$ 条道路构成，城市与道路都从 $1$ 开始编号，其中 $1$ 号城市是 H 国的首都。H 国中一条道路将把两个不同城市直接相连，且任意两个城市间至多有一条道路。
H 国是一个信奉魔法的国家，在第 $j$ 天，$i$ 号城市的魔法值为 $f_{i,j}$。H 国的魔法师已观测到第 $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 \geq 1$，$v_{1}, v_{2}, \cdots, v_{k}$ 是所有与 $x$ 号城市直接相连的城市，$\oplus$ 为异或运算。
现在 H 国的国王问了你 $q$ 个问题，对于第 $i(1 \leq i \leq q)$ 个问题你需要回答：第 $a_i$ 天时首都的魔法值是多少。
思路
对城市的连通性建立邻接矩阵，如果两个点直接相连则为 $1$，否则为 $0$。设该 01 矩阵为 $A$。则
$$f_{x,i}=f_{1,i-1}\times A_{1,x}\oplus f_{2,i-1}\times A_{2,x}\oplus\cdots\oplus f_{n,i-1}\times A_{n,x}$$
和矩阵乘法一模一样，只是加法换成了异或。下文中的乘号都代表这种运算。
设 $i$ 为天数，$j$ 为城市编号，则有 $f_i=f_{i-1} \times A$，即 $f_i=f_0 \times A^i$。
但要想用矩阵优化还需要这种运算符合结合律，即对矩阵 $A,B,C$，有 $A \times (B \times C)=(A \times B) \times C$。当 $A,B,C$ 全是 01 矩阵的时候，结合律成立。
所以可以用矩阵快速幂的思想，预处理出所有 $A^{2^i}$，然后再二进制拆分每个 $a_i$，累计为 $1$ 的相应位上的矩阵得到每个询问的答案。
代码
#include<bits/stdc++.h>
using namespace std;
struct node{
long long x,y,s[105][105];
};
long long n,m,q;
node mul(node a,node b){
node ans;
memset(ans.s,0,sizeof(ans.s));
ans.x=a.x;
ans.y=b.y;
for (long long i=1;i<=a.x;i++){
for (long long j=1;j<=b.y;j++){
for (long long k=1;k<=a.y;k++){
ans.s[i][j]^=a.s[i][k]*b.s[k][j];
}
}
}
return ans;
}
node f,pre[50];
long long solve(long long x){
node ans;
ans=f;
for (int i=0;i<=33;i++){
if ((x>>i)&1){
ans=mul(ans,pre[i]);
}
}
return ans.s[1][1];
}
int main(){
cin>>n>>m>>q;
f.x=1;f.y=n;
for (int i=1;i<=n;i++){
cin>>f.s[1][i];
}
memset(pre[0].s,0,sizeof(pre[0].s));
pre[0].x=n;
pre[0].y=n;
for (int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
pre[0].s[a][b]=1;
pre[0].s[b][a]=1;
}
for (int i=1;i<=33;i++){
pre[i]=mul(pre[i-1],pre[i-1]);
}
for (int i=1;i<=q;i++){
long long x;
cin>>x;
cout<<solve(x)<<endl;
}
}
%%%
主题不错，值得学习借鉴
洛谷蒟蒻路过
%%%
同为OI圈我觉得我是个垃圾
7878979979
ヾ(≧∇≦*)ゝ
666