能量采集
题目描述
**题面已修改,请大家注意。**
请你求下列式子:$\sum_{i=1}^N\sum_{j=1}^Ngcd(i,j)$ ,答案对大质数取模。
不好意思读错剧本了。
给定一个 $n$ 个点 $m$ 条边的有向图,每个点有初始能量 $a_i$ 。
每过一秒,每个点的能量便会等量地流向所有出边,另外,会有一份流向自己(你可以当做有一个自环)。
现在 $dkw$ 有 $q$ 次询问,每次询问会给你一个时间 $t$ ,$dkw$想知道 $t$ 秒时每个点的能量。
不保证图中没有重边和自环,答案对$998244353$取模。
输入输出格式
输入格式
第一行包含三个整数,$n,m,q$ 。
第二行包含$n$个整数,从$a_1$到$a_n$ ,代表初始能量。
接下来 $m$ 行,每行包含两个正整数 $x_i,y_i$ ,代表一条有向边,从 $x_i$ 指向 $y_i$ ,我们约定点编号从 $1$ 到 $n$ 。
接下来 $q$ 行,每行包含一个正整数 $t$ ,代表一次询问。
输出格式
为了防止输出过大,对于每个询问你只需要输出一行一个非负整数,代表 $n$ 个点的能量(取模)的异或和对$998244353$取模的结果。
输入输出样例
输入样例 #1
5 10 3
4 5 3 2 7
4 1
1 4
2 1
3 2
1 2
5 1
2 4
2 1
2 4
1 4
1
2
3
输出样例 #1
15
548614965
80769513
说明
对于 30% 的数据,$1\le t \le 50$
对于 60% 的数据,$1\le q\le 50$
对于 80% 的数据,$1\le q\le 1000$
对于 100% 的数据,$1\le n\le 50,1\le m\le n\times (n-1),1\le q\le 5\times 10^4,0< a_i< 998244353,1\le t\le 10^9$