[NOI Online 3 提高组] 魔法值 题解

前言

好题,考的时候用循环节做法水了部分分。看上去是图论实际上是矩阵乘(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;
	}
}

评论

  1. 刘渤源
    Windows Edge

    同为OI圈我觉得我是个垃圾

    2周前
    2020-7-24 9:49:58
  2. hello
    Windows Chrome

    666

    2月前
    2020-5-29 10:18:08

发送评论 编辑评论


				
上一篇
下一篇