問題一覧 > 通常問題

No.2816 At Most Two Moves

レベル : / AI推定難易度 : 1400 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 58
作問者 : hirayuu_yc / テスター : highlighter Magentor Yoyoyo8128 zeta7532 fact493 warabi0906
お気に入りにしたユーザー ProblemId : 10796 / 自分の提出
問題文最終更新日: 2024-07-19 21:19:47
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 437 ('09 Contest 002 day2) (順位表) の他の問題:

Problem Statement

For every tournament graph with $N$ vertices numbered $1,2,\dots,N$, find the value "the number of vertices reachable from vertex $1$ by moving along edges at least $0$ and at most $2$ times", and output the sum of these values modulo $998244353$.

You are given $T$ test cases; answer each of them.

What is a tournament graph with $N$ vertices? A tournament graph with $N$ vertices is a simple directed graph such that, for every pair of integers $(i,j)$ satisfying $1\leq i< j\leq N$, exactly one of "a directed edge from vertex $i$ to vertex $j$" or "a directed edge from vertex $j$ to vertex $i$" exists, and no other edges exist.

Input

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

Each test case is given in the following format.

$N$
  • $1\leq T\leq 1000$
  • $1\leq N\leq 10^{9}$
  • All input values are integers.

Output

Output $T$ lines.

On the $i$-th line, output the answer for the $i$-th test case.

Sample

Sample 1
Input
5
1
2
3
4
100
Output
1
3
18
202
140791901

A directed edge from vertex $i$ to vertex $j$ is denoted as edge $i\to j$.

  • For the $2$-nd test case, the following $2$ graphs are possible.
    • The graph consisting of edge $1\to 2$: vertex $1$ can be reached with $0$ moves, and vertex $2$ can be reached with $1$ move.
    • The graph consisting of edge $2\to 1$: vertex $1$ can be reached with $0$ moves, but vertex $2$ cannot be reached.
  • For the $4$-th test case, note that vertices that cannot be reached without moving $3$ or more times are not counted.
  • For the $5$-th test case, do not forget to compute the answer modulo $998244353$.

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