description
solution:
这道题关于矩阵。。原来根本不会啊啊
我们记(e_{i,j}=0/1)表示i到j是否有直接连边
由于原图是一个无向图，所以(e_{i,j}=e_{j,i})
那么原图中的等式
(f_{x,j}=f_{v_1,j-1}⊕f_{v_2,j-1}⊕...⊕f_{v_k,j-1})
就可以转化为
(f_{x,j}=e_{x,1}*f_{1,j-1}⊕e_{x,2}*f_{2,j-1}⊕...⊕e_{x,n}*f_{n,j-1})
也就是说
不过这里矩阵乘法的定义有些不同。
这里将矩阵乘法中的“加法”变为“异或”
于是乎第j天的(f)就可以通过矩阵快速幂做出来
但是这么做的前提条件就是这种“新式矩阵”像普通矩阵那样满足结合律
这是比较好证明的，直接可以根据(e)为(0/1)分类讨论可以证明(同时这个01矩阵若干次幂后仍然是01矩阵，因为每次最后都是异或起来的)
具体来说，相当于要证明：(A*(B*C)=(A*B)*C)
发现如果证明(A*(B*C)=A*B*C=(A*B)*C)则原命题成立
考虑乘出来之后的矩阵：(M_{i,j}=XOR_{x=1}^nA_{i,x}*XOR_{y=1}^mB_{x,y}*C_{y,j})
是否等价于(M`_{i,j}=XOR_{x=1}^nXOR_{y=1}^mA_{i,x}*B_{x,y}*C_{y,j})
当(A_{i,x}==0)时显然二者在x处是等价的
当(A_{i,x}==1)时发现也是等价的
因此结论得证。另一边同理可证。因此这种新的矩阵乘法满足结合律。
然后考虑到有多次询问，我们可以预处理原矩阵的2的整数次幂
对于每次询问就可以直接(O(logn))次矩乘求出来
#include<bits/stdc++.h>
using namespace std;
typedef unsigned int uint;
const int N=105,LOG=32;
uint n,m,q;
struct Matrix
{
uint c[N][N];
inline void pre(){memset(c,0,sizeof(c));}
}M[LOG],f;
Matrix mul(const Matrix&x,const Matrix&y,uint a=n,uint b=n,uint c=n)
{
Matrix z;
for(uint i=1;i<=a;++i)
for(uint j=1;j<=c;++j)
{
z.c[i][j]=0;
for(uint k=1;k<=b;++k)
z.c[i][j]^=x.c[i][k]*y.c[k][j];
}
return z;
}
int main()
{
scanf("%u%u%u",&n,&m,&q);
M[0].pre(),f.pre();
for(uint i=1;i<=n;++i)scanf("%u",&f.c[i][1]);
for(uint i=1;i<=m;++i)
{
uint x,y;scanf("%u%u",&x,&y);
M[0].c[x][y]=M[0].c[y][x]=1;
}
for(uint i=1;i<LOG;++i)M[i]=mul(M[i-1],M[i-1]);
while(q--)
{
uint a;scanf("%u",&a);
Matrix ans=f;
for(uint i=0;(1ll<<i)<=a;++i)
if(a&(1ll<<i))ans=mul(M[i],ans,n,n,1);
printf("%u
",ans.c[1][1]);
}
return 0;
}
p.s.
一点关于邻接矩阵的小拓展
-
对于无权图
(e_{i,j}=0/1)为初始的邻接矩阵
那么(e`_{i,j}=sum_k e_{i,k}*e_{k,j})是什么意义呢
考虑加法原理和乘法原理
可以发现这其实就是(i)到(j)长度为2的路径的条数
以此类推可知邻接矩阵的k次方就是从一个点到一个点长度为k的路径的条数（甚至路径可以不是简单路径） -
对于有权图
邻接矩阵(e_{i,j})表示直接连接i->j边的长度（若没有设为正无穷）
我们将原来矩阵乘法中的“乘法”改为“加法”，将“加法”改为“取最小值”
例如：(M_{i,j}=min_{k=1}^n(A_{i,k}+B_{k,j}))
于是乎初始邻接矩阵的n次幂后得到的结果就是任意两点之间的最短路
这个东西似乎和Floyd有不少联系呢