問題一覧 > 通常問題

No.1116 Cycles of Dense Graph

レベル : / AI推定難易度 : 2300 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 32
作問者 : 37zigen / テスター : hotman78
お気に入りにしたユーザー ProblemId : 4557 / 自分の提出
問題文最終更新日: 2026-10-22 17:54:01
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 257 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。