No.1116 Cycles of Dense Graph
Problem Statement
There is a complete graph $G$ with $N$ vertices, where the vertices are labeled $1,\ldots,N$.
Find the number of cycles, modulo $998244353$, in the subgraph obtained by removing the $M$ edges $\{a_i,b_i\}\ (1 \leq i \leq M)$ from the graph $G$.
A cycle is a graph $(V,E)$ given as follows.
$$
\begin{align}
&V=\{x_0,\ldots,x_k\}\\
&E=\{x_0x_1,x_1x_2,\ldots,x_{k-1}x_k,x_kx_0\}
\end{align}
$$
Here, $k \geq 2$ and all $x_i$ are distinct.
Input
$N\ M$ $a_1\ b_1$ $\vdots$ $a_M\ b_M$
$1 \leq N \leq 10^5$
$0 \leq M \leq \min(N(N-1)/2,15)$
$1 \leq a_i,b_i \leq N$
$a_i \neq b_i$
$\{a_i , b_i\} \neq \{a_j, b_j\} \ (i\neq j)$
Output
Print a newline at the end.
Sample
Sample 1
Input
3 1 1 2
Output
0
Sample 2
Input
4 0
Output
7
The following are the 7 cycles contained in $K_4$.
Sample 3
Input
6 5 1 3 2 4 3 5 4 1 5 2
Output
21
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
37zigen
hotman78