問題一覧 > 通常問題

No.2985 May Count Induced C4 Subgraphs

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 10
作問者 : 👑 NachiaNachia
7 ProblemId : 11692 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-12-09 02:33:59

注意

実行時間制限は $5$ 秒ですが、結構厳しいです。

問題文

非負整数 $T$ ( $0\leq T\leq 998\, 244\, 352$ ) を自由に選び、以下の問題を解いてください。

$N$ 頂点 $M$ 辺の無向単純グラフが与えられます。 頂点と辺はそれぞれ $1$ から順に番号がついています。 $i$ 番目の辺は頂点 $U_i$ と頂点 $V_i$ を結びます。

このグラフの $4$ 頂点の選び方であって、それらの誘導部分グラフが

  • 辺をもたないものの個数を $A$ 、
  • 辺をちょうど $4$ つもち、それらが長さ $4$ のサイクルをなすものの個数を $B$

とします。 $A+TB$ を $998\, 244\, 353$ で割ったあまりを求めてください。

制約

  • $1\leq N\leq 2\times 10^5$
  • $0\leq M\leq 2\times 10^5$
  • $U_i \neq V_i$
  • $i\neq j$ ならば $\lbrace U_i,V_i\rbrace \neq \lbrace U_j,V_j\rbrace$
  • 入力はすべて整数

入力

$N$ $M$
$U_1$ $V_1$
$U_2$ $V_2$
$\vdots$
$U_M$ $V_M$

出力

$T$ の値と、 $A+TB$ を $998\, 244\, 353$ で割ったあまりを、この順に空白区切りで $1$ 行に出力してください。最後に改行してください。

サンプル

サンプル1
入力
6 4
1 2
2 3
3 4
4 1
出力
10000 20001

辺をもたない誘導部分グラフは、頂点集合で表すと $\lbrace 1,3,5,6\rbrace , \lbrace 2,4,5,6\rbrace$ の $2$ 個です。

辺をちょうど $4$ つもち、それらが長さ $4$ のサイクルをなすような誘導部分グラフは、頂点集合で表すと $\lbrace 1,2,3,4\rbrace$ の $1$ 個です。

$A=2$ , $B=1$ なので、 $T=10000$ を選んだ場合の答えは $2\times 10000 + 1=20001$ です。

サンプル2
入力
3 3
1 2
2 3
1 3
出力
99999 0

$A=B=0$ です。

サンプル3
入力
10 17
1 4
1 6
1 10
3 4
3 5
4 5
4 6
4 9
4 10
5 7
5 8
5 9
6 8
6 10
7 9
7 10
9 10
出力
0 13

$A=13$ , $B=2$ です。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。