觀察數(shù)據(jù)范圍發(fā)現(xiàn) \(n\) 很小而 \(t\) 很大，于是我們想到矩陣快速冪。我們可以直接建 \(n \times n\) 的轉移矩陣 \(A\)，設 \(u\) 的出邊為 \(d_u\) 條，邊 \((u,v)\) 共有 \(cnt_{(u,v)}\) 條（注意重邊要計算多次即 \(cnt_{(u,v)}\) 可能大于一），則 \(A_{v,u} \equiv \dfrac{cnt_{(u,v)}}{d_u} \pmod {998244353}\)，再定義 \(n \times 1\) 的初始矩陣 \(B\) 其中 \(B_{i,1} \equiv a_i \pmod {998244353}\)。則詢問 \(t\) 的答案即為 \(A^t \times B\)。此時時間復雜段為 \(\mathcal{O}(qn^3 \log t)\)，卡卡常能過不太能過。

我們考慮進行優(yōu)化。我們考慮快速冪的過程，據(jù)一個例子 \(t=13\)，則我們實際計算的是 \(A^8 \times A^4 \times A^1 \times B\)。而矩陣乘法具有結合律，我們可以優(yōu)化計算順序：\(A^8 \times (A^4 \times (A^1 \times B))\)，我們發(fā)現(xiàn) \(A^{2^k}\) 與 \(B\) 相乘的復雜度僅為 \(\mathcal{O}(n^2)\)，而由于轉移矩陣是已知的，那么 \(A^{2^k}\) 是可以預處理的。于是我們成功把時間復雜度降為了 \(\mathcal{O}(n^3 \log t + qn^2 \log t)\)，能過。

// 火車頭
const int mod=998244353;
const int N=55;

struct Matrix {
	int n,m,a[N][N];
	Matrix(int l=0,int c=0) {
		n=l,m=c,memset(a,0,sizeof(a));
		return ;
	}
	inline void init(int d) {
		n=m=d,memset(a,0,sizeof(a));
		for(int i=1;i<=d;i++) a[i][i]=1;
		return ;
	}
	inline Matrix operator *(const Matrix &tmp) const {
		Matrix res(n,tmp.m);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				for(int k=1;k<=tmp.m;k++)
					add(res.a[i][k],(ll)a[i][j]*tmp.a[j][k]%mod);
		return res;
	}
};

int n,m,q;
vector<int> edge[N];
Matrix ret[30],stat;

inline ll quickpow(ll base,ll p) {
	ll tmp=1;
	for(;p;p>>=1) {
		if(p&1) tmp=tmp*base%mod;
		base=base*base%mod;
	}
	return tmp;
}
inline Matrix quickpow_matrix(ll p) {
	Matrix tmp=stat;
	for(int i=0;i<30;i++)
		if((p>>i)&1) tmp=ret[i]*tmp;
	return tmp;
}

int main() {
	read(n),read(m),read(q);
	stat=Matrix(n,1);
	for(int i=1;i<=n;i++) read(stat.a[i][1]),edge[i].pb(i);
	for(int i=1,u,v;i<=m;i++) read(u),read(v),edge[u].pb(v);
	ret[0]=Matrix(n,n);
	for(int i=1;i<=n;i++) {
		ll c=quickpow(edge[i].size(),mod-2);
		for(int v:edge[i]) add(ret[0].a[v][i],c);
	}
	for(int i=1;i<30;i++) ret[i]=ret[i-1]*ret[i-1];
	for(int i=1,t;i<=q;i++) {
		read(t);
		Matrix res=quickpow_matrix(t);
		ll ans=0;
		for(int i=1;i<=n;i++) ans^=res.a[i][1];
		write(ans%mod),_E;
	}
	return 0;
}

點個贊再走喵 qaq