#P14524. [2026年省队模拟联测]图

    ID: 13741 传统题 8000ms 1024MiB 尝试: 2 已通过: 1 难度: 9 上传者: 标签>组合数学图论动态规划多项式与生成函数FFTCF2800状压DP数位DP模拟

[2026年省队模拟联测]图

图(graph)

题目描述

给定一张含有 nn 个点的无向简单图,你需要给每个点 ii 赋一个点权 bib_i,满足有边相邻的两个点点权不同。

求出满足

∀i, 0≤bi≤ai\forall i,\ 0\le b_i\le a_i

且

$$b_1\mathbin{\operatorname{xor}}b_2\mathbin{\operatorname{xor}}\cdots\mathbin{\operatorname{xor}}b_n=C$$

的赋权方案数,答案对 998244353998244353 取模。

输入格式

第一行三个整数 n,m,Cn,m,C。

第二行 nn 个整数,第 ii 个表示 aia_i。

接下来 mm 行,每行两个整数 ui,viu_i,v_i,表示图上的一条无向边 (ui,vi)(u_i,v_i)。

输出格式

输出一行一个整数,表示答案。

样例 1

输入

3 1 2
1 2 3
1 2

输出

4

样例 2

输入

4 6 2
7 11 14 0
1 2
1 3
2 3
2 4
4 1
4 3

输出

44

数据范围与约定

测试数据满足 1≤n≤151\le n\le15,0≤m≤n(n−1)20\le m\le\dfrac{n(n-1)}2,0≤ai,C≤10180\le a_i,C\le10^{18}。

子任务编号 特殊性质 分值
11 n≤5, ai≤15n\le5,\ a_i\le15 1010
22 n≤13n\le13 5050
33 m=0m=0 1515
44 无 2525