1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
| #include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define fi first
#define se second
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 55, M = 5e4 + 5;
const ll LINF = 1e18 + 5;
constexpr int mod = 998244353;
int n, m, q, qry[M], idx[M], res[M];
ll inv[N];
struct matrix
{
int n, m;
ll mat[N][N];
matrix() { memset(mat, 0, sizeof(mat)); }
matrix(int a, int b) : n(a), m(b) { memset(mat, 0, sizeof(mat)); }
void one()
{
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
mat[i][j] = (i==j);
}
}b[32];
matrix operator * (matrix a, matrix b)
{
matrix res(a.n, b.m);
for(int i=1; i<=a.n; i++)
for(int j=1; j<=b.m; j++)
for(int k=1; k<=a.m; k++)
res.mat[i][j] = (res.mat[i][j]+a.mat[i][k]*b.mat[k][j]%mod)%mod;
return res;
}
matrix operator ^ (matrix a, ll x)
{
matrix res; res.one();
while(x)
{
if(x&1) res = res * a;
a = a * a;
x >>= 1;
}
return res;
}
int main()
{
scanf("%d%d%d", &n, &m, &q);
matrix a(n, 1);
for(int i=1; i<=n; i++) scanf("%lld", &a.mat[i][1]);
b[0].n = b[0].m = n;
b[0].one();
for(int i=1; i<=m; i++)
{
int u, v; scanf("%d%d", &u, &v);
b[0].mat[v][u]++;
}
inv[0] = inv[1] = 1;
for(int i=2; i<=n; i++) inv[i] = (mod-mod/i)*inv[mod%i]%mod;
for(int j=1; j<=n; j++)
{
int d = 0;
for(int i=1; i<=n; i++) d += b[0].mat[i][j];
for(int i=1; i<=n; i++) b[0].mat[i][j] = b[0].mat[i][j]*inv[d]%mod;
}
for(int i=1; i<=31; i++) b[i] = b[i-1]*b[i-1];
for(int i=1; i<=q; i++) scanf("%d", qry+i);
iota(idx+1, idx+q+1, 1);
sort(idx+1, idx+q+1, [](int x, int y) {
return qry[x] < qry[y];
});
matrix ans = a;
for(int i=1; i<=q; i++)
{
int tmp = qry[idx[i]] - qry[idx[i-1]];
for(int j=31; j>=0; j--)
if((tmp>>j)&1) ans = b[j]*ans;
ll Res = 0;
for(int i=1; i<=n; i++) Res ^= ans.mat[i][1];
res[idx[i]] = Res%mod;
}
for(int i=1; i<=q; i++) printf("%d\n", res[i]);
return 0;
}
|