#2934. [GDKOI]异或图

[GDKOI]异或图

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一张 nn 个点 mm 条边的无向图和一个长度为 nn 的数组 a1,a2,,ana_1, a_2, ··· , a_n 以及一个整数 CC,你需要求出有 多少个长度为 nn 的数组 bb 满足:

1. 0biai1in0 ≤ b_i ≤ a_i,∀1 ≤ i ≤ n

2. 对于每条边 (u,v)bubv(u, v),bu \neq bv

3. b1b2bn=Cb_1 ⊕ b_2 ⊕ · · · ⊕ b_n = C ,其中 代表异或。

答案对 998244353998244353 取模。

输入格式

第一行输入三个整数 n,m,cn, m, c

第二行输入 nn 个整数 a1,a2,,ana_1, a_2,··· , a_n

接下来的 mm 行,每行输入两个正整数 u,vu, v,表示一条无向边。

输出格式

一行一个整数表示答案。

输入样例1

3 1 2
1 2 3
1 2

输出样例1

4

输入样例2

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

输出样例1

44

样例解释

可行的 bb 数组有 (0,1,3),(0,2,0),(1,0,3),(1,2,1)(0,1,3),(0,2,0),(1,0,3),(1,2,1) 四种

数据范围

对于所有数据,满足 1n15,0mn(n1)2,0ai,C10181 ≤ n ≤ 15,0 ≤ m ≤ \frac{n(n-1)}{2} , 0 ≤ a_i, C ≤ 10^{18}

subtask1(20pts)subtask1(20pts)n5,0ai,C15n ≤ 5, 0 ≤ a_i, C ≤ 15

subtask2(50pts)subtask2(50pts)n13n ≤ 13

subtask3(10pts)subtask3(10pts)m=0m = 0

subtask4(20pts)subtask4(20pts):无特殊限制。

GDKOI提高组重现

未参加
状态
已结束
规则
IOI
题目
6
开始于
2023-3-15 21:00
结束于
2023-3-25 21:00
持续时间
240 小时
主持人
参赛人数
12