洛谷 P6569 【NOI Online #3 提高组】魔法值 题解

洛谷 P6569 【NOI Online #3 提高组】魔法值 题解

xiaoh 2020-7-13

题意

给定一张有$n$个点，$m$条边的无向图，每个点上有一个权值$f_i$，每一天每一个点的权值会变为与其直接相连的所有点的点权异或和。现有$q$个询问，每次询问一个日期$a_i$，求第$a_i$天$1$号点的点权。

数据范围：

$1\leq n,q\leq 100,1\leq m\leq \frac{n(n-1)}{2}且无重边,0\leq a_i,f_i< 2^{32}$

题解

首先，题意可转化为“通过恰好$a_i$步可以走到$1$号点的所有路径的初始点的点权异或和”，那么由此联想到熟悉的矩阵乘法。由于异或和加法类型相同，经过观察我们发现它也满足矩阵乘的交换律等性质，因为我们可以每次用矩阵进行转移，每一次询问的复杂度为$O(n^3\log a)$，显然再乘上一个$q$以后时间会爆炸，所以我们考虑如何进行优化。注意到向量乘矩阵的复杂度是$O(n^2)$的，所以我们不妨将所有$2$的次幂的矩阵先预处理出来，然后每次用$f$序列作为向量去乘我们预处理好的矩阵，可以使询问的复杂度少掉一个$n$,同时预处理的复杂度为$O(n^3\log a)$，显然这是可以通过的，所以总的复杂度为$O(n^3\log a+n^2q\log a)$。

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=110,LOGN=32;
int n,m,q;
struct Matrix{
    int a[MAXN][MAXN];
    inline void init()
    {
        memset(a,0,sizeof(a));
    }
    inline Matrix mul(Matrix x)
    {
        Matrix ret;
        ret.init();
        for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
        for(int k=1;k<=n;++k) ret.a[i][j]^=a[i][k]*x.a[k][j];
        return ret;
    }
}f[LOGN];
struct Vector{
    long long a[MAXN];
    inline void init()
    {
        memset(a,0,sizeof(a));
    }
    inline Vector mul(Matrix x)
    {
        Vector ret;
        ret.init();
        for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j) ret.a[i]^=a[j]*x.a[j][i];
        return ret;
    }
}a;
inline void prework()
{
    for(int i=1;i<LOGN;++i) f[i]=f[i-1].mul(f[i-1]);
}
inline long long solve(long long x)
{
    Vector ret=a;
    for(int i=LOGN-1;i>=0;--i)
    if(x>=(1ll<<i)) ret=ret.mul(f[i]),x-=(1ll<<i);
    return ret.a[1];
}
int main()
{
    read(n),read(m),read(q);
    for(int i=1;i<=n;++i) read(a.a[i]);
    for(int i=1;i<=m;++i)
    {
        int u,v;
        read(u),read(v);
        f[0].a[u][v]=f[0].a[v][u]=1;
    }
    prework();
    for(int i=1;i<=q;++i)
    {
        long long x;
        read(x);
        write(solve(x)),putchar('\n');
    }
	return 0;
}