8222: [yosupo] Graph - Enumerate Cliques
[Creator : ]
Description
You are given a simple undirected graph $G$, consisting of $N$ vertices and $M$ edges.The $i$-th edge of $G$ is $\lbrace u_i, v_i \rbrace$.Each vertex of $G$ has an integer value, and the value of $i$ th vertex is $x_i$.
Find the sum of $\displaystyle \prod_{i \in C} x_i$ over all non-empty cliques $C$ of $G$, and print the sum modulo $998,244,353$ .
Find the sum of $\displaystyle \prod_{i \in C} x_i$ over all non-empty cliques $C$ of $G$, and print the sum modulo $998,244,353$ .
Input
$N$ $M$
$x_0$ $x_1$ $\ldots$ $x_{N-1}$
$u_0$ $v_0$
$u_1$ $v_1$
$\vdots$
$u_{M-1}$ $v_{M-1}$
$x_0$ $x_1$ $\ldots$ $x_{N-1}$
$u_0$ $v_0$
$u_1$ $v_1$
$\vdots$
$u_{M-1}$ $v_{M-1}$
Output
$A$
Constraints
$1 \le N \le 100$
$1 \le M \le 100$
$0 \le x_i \lt 998,244,353$
$0 \le u_i \lt N$
$0 \le v_i \lt N$
$u_i \neq v_i$
$\lbrace u_i, v_i \rbrace \neq \lbrace u_j, v_j \rbrace \ (i \neq j)$
$1 \le M \le 100$
$0 \le x_i \lt 998,244,353$
$0 \le u_i \lt N$
$0 \le v_i \lt N$
$u_i \neq v_i$
$\lbrace u_i, v_i \rbrace \neq \lbrace u_j, v_j \rbrace \ (i \neq j)$
Sample 1 Input
3 2
1 2 3
0 1
1 2
Sample 1 Output
14
$(0), (1), (2), (0, 1), (1, 2)$ are cliques of $G$.
Print $14$, which is the result of $1 + 2 + 3 + 1 \cdot 2 + 2 \cdot 3 \bmod 998,244,353$ .
Print $14$, which is the result of $1 + 2 + 3 + 1 \cdot 2 + 2 \cdot 3 \bmod 998,244,353$ .
Sample 2 Input
5 9
97644645 128903910 346967627 176460807 156955500
0 1
0 2
0 3
0 4
1 2
1 3
1 4
2 3
2 4
Sample 2 Output
664902553