No.2816 At Most Two Moves
レベル :
/ AI推定難易度 : 1400
/ 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 58
作問者 :
hirayuu_yc
/ テスター :
highlighter
Magentor
Yoyoyo8128
zeta7532
fact493
warabi0906
タグ : / 解いたユーザー数 58
作問者 :
highlighter
Magentor
fact493
問題文最終更新日: 2024-07-19 21:19:47
English (AI translation)
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
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もしくは右上の雲マークをクリックしてアカウントを作成してください。