Enumerate Triangles

AC一覧

Problem Statement
問題文

You are given a simple undirected graph, consisting of $N$ vertices and $M$ edges. The $i$-th edge is $\lbrace u_i, v_i \rbrace$. Each vertex has an integer value, and the value of $i$ th vertex is $x_i$.

Three vertices $a, b, c (a \lt b \lt c)$ connected by three edges $\lbrace a, b \rbrace, \lbrace a, c \rbrace, \lbrace b, c \rbrace$ are called triangle. Find the sum of $x_a x_b x_c$ over all triangles, and print the sum modulo $998{,}244{,}353$ .

$N$ 頂点 $M$ 辺の単純無向グラフが与えられます。 $i$ 番目の辺は $\lbrace u_i, v_i \rbrace$ です。 各頂点 $i$ には整数 $x_i$ が割り当てられています。

3 頂点 $a, b, c (a \lt b \lt c)$ であって辺 $\lbrace a, b \rbrace, \lbrace a, c \rbrace, \lbrace b, c \rbrace$ が全て存在するものを triangle と呼びます。 全ての triangle についての $x_a x_b x_c$ の和を $998{,}244{,}353$ で割った余りを求めてください。

Constraints
制約

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}$

Output
出力

$A$

Sample
サンプル

# 1

4 5
1 2 3 4
0 3
2 0
2 1
2 3
1 3
36

$0, 2, 3$ and $1, 2, 3$ are triangles. Print $36$, which is the result of $1 \cdot 3 \cdot 4 + 2 \cdot 3 \cdot 4 \bmod 998{,}244{,}353$ .

$0, 2, 3$ 及び $1, 2, 3$ が triangle です。 $1 \cdot 3 \cdot 4 + 2 \cdot 3 \cdot 4$ を $998{,}244{,}353$ で割った余りである $36$ を出力します。


Forum


Timelimit: 5 secs

Before submitting, please confirm terms and conditions