P10104 [GDKOI2023 Senior] XOR Graph

Given an undirected graph with $n$ vertices and $m$ edges, an array $a_1, a_2, \cdots , a_n$ of length $n$, and an integer $C$, you need to count how many arrays $b$ of length $n$ satisfy: 1. $0 \le b_i \le a_i, \forall 1 \le i \le n$。 2. For every edge $(u, v)$, $b_u \ne b_v$。 3. $b_1 \oplus b_2 \oplus \cdots \oplus b_n = C$, where $\oplus$ denotes bitwise XOR. Output the answer modulo $998244353$。

The first line contains three integers $n, m, c$。 The second line contains $n$ integers $a_1, a_2, \cdots , a_n$。 The next $m$ lines each contain two positive integers $u, v$, representing an undirected edge。

Output one integer, the answer。

There are four feasible arrays $b$: $(0, 1, 3), (0, 2, 0), (1, 0, 3), (1, 2, 1)$。 For all testdata, $1 \le n \le 15$, $0 \le m \le \frac{n(n-1)}{2}$, $0 \le a_i, C \le 10^{18}$。 - Subtask 1 (20pts): $n \le 5$, $0 \le a_i, C \le 15$。 - Subtask 2 (50pts): $n \le 13$。 - Subtask 3 (10pts): $m = 0$。 - Subtask 4 (20pts): No special constraints。 Translated by ChatGPT 5