No.2816 At Most Two Moves

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 59
作問者 :

hirayuu_yc / テスター :

highlighter

Magentor

Yoyoyo8128

zeta7532

fact493

warabi0906

0 ProblemId : 10796 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2024-07-19 21:19:47

頂点に $1,2,\dots,N$ と番号が振られた $N$ 頂点のトーナメントグラフすべてについて「頂点 $1$ から $0$ 回以上 $2$ 回以下辺に沿って移動することで到達できる頂点の数」の値を求め、その総和を $998244353$ で割った余りを出力してください。

$T$ 個のテストケースが与えられるので、それぞれについて答えてください。

N

頂点のトーナメントグラフとは？

$N$ 頂点のトーナメントグラフとは、

1\leq i< j\leq N

を満たすすべての整数の組

(i,j)

について、「頂点

i

から頂点

j

に向かう有向辺」または「頂点

j

から頂点

i

に向かう有向辺」のちょうど一方が存在し、それ以外の辺は存在しない単純有向グラフのことです。

 $T$ 
 $\text{testcase}_1$ 
 $\text{testcase}_2$ 
 $\vdots$ 
 $\text{testcase}_T$

各テストケースは以下の形式で与えられる。

$N$

$T$ 行出力してください。

$i$ 行目には、第 $i$ テストケースに対しての答えを出力してください。

頂点 $i$ から頂点 $j$ に向かう有向辺のことを辺 $i\to j$ と表します。

第 $2$ テストケースについて、以下の $2$ 通りのグラフが考えられます。
- 辺 $1\to 2$ からなるグラフ: 頂点 $1$ には $0$ 回、頂点 $2$ には $1$ 回移動することで到達できます。
- 辺 $2\to 1$ からなるグラフ: 頂点 $1$ には $0$ 回の移動で到達できますが、頂点 $2$ には到達できません。
第 $4$ テストケースについて、 $3$ 回以上移動しないと到達することのできない頂点は数えないことに注意してください。
第 $5$ テストケースについて、答えを $998244353$ で割った余りを求めることを忘れないでください。

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