問題一覧 > 通常問題

No.2816 At Most Two Moves

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 54
作問者 : hirayuu_ychirayuu_yc / テスター : highlighterhighlighter MagentorMagentor Yoyoyo8128Yoyoyo8128 zeta7532zeta7532 fact493fact493 warabi0906warabi0906
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$
  • $1\leq T\leq 1000$
  • $1\leq N\leq 10^{9}$
  • 入力はすべて整数

出力

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

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

サンプル

サンプル1
入力
5
1
2
3
4
100
出力
1
3
18
202
140791901

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