問題一覧 > 通常問題

No.3175 Teleportation Labyrinth (Easy)

レベル : / AI推定難易度 : 1650 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 22
作問者 : t98slider / テスター : akakimidori
お気に入りにしたユーザー ProblemId : 11953 / 自分の提出
問題文最終更新日: 2026-10-22 16:44:04
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 469 (順位表) の他の問題:

Preface

This problem differs from the Hard version only in the size of the constraint on $N$.

Problem Statement

Yukishii has become lost in the Teleportation Labyrinth.
In the vicinity of the Teleportation Labyrinth (including the Teleportation Labyrinth itself) there exist rooms numbered from room $-10^{100}$ to room $10^{100}$, and the $N$ rooms from room $1$ to room $N$ are assigned to the Teleportation Labyrinth.
Each of the $N$ rooms in the Teleportation Labyrinth contains $1$ monster.

Every time Yukishii visits room $x$ ($1 \leq x \leq N$), she fights a monster, and when she defeats the monster in room $x$, the following teleportation occurs.

  • Choose $d$ uniformly at random from the $2K+1$ integers satisfying $-K \leq d \leq K$.
  • From room $x$, she is teleported to room $x + d$.
    (Note that a teleportation from room $x$ to room $x$ is possible.)
Each time Yukishii teleports, the monsters are placed again, and when she teleports to a room that is not one of room $1$ through room $N$, she is considered to have escaped from the Teleportation Labyrinth.
For each case where Yukishii starts exploring from room $i$ ($1 \leq i \leq N$), find the expected number of monsters she needs to defeat before escaping from the Teleportation Labyrinth, modulo $\bmod 998244353$. More precisely, when the expected value is represented as an irreducible fraction $P/Q$, within the given constraints there is a unique integer $R$ satisfying $R \times Q≡P (\bmod 998244353), 0 \leq R < 998244353$, so output that $R$.

Constraints

  • $1 \leq N \leq 500$
  • $1 \leq K \leq 20$
  • The sum of $N$ over all test cases does not exceed $500$.
  • All inputs are integers.
  • Test cases whose names contain the string evil do not satisfy the constraints, but they do not affect AC. The constraints for the test cases containing evil are
    $1 \leq N \leq 3 \times 10^5$, $1 \leq A_i \leq N\ (1 \leq i \leq N)$.

Input

The input is given from standard input in the following format, where $\mathrm{case}_i ~ (i = 1, 2, \cdots, T)$ is the $i$-th test case.

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

Each test case is given in the following format.

$N$ $K$

Output

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

For each test case, let $x_{i}$ be the expected number of monsters Yukishii needs to defeat before escaping from the Teleportation Labyrinth when she starts exploring from room $i$ ($1 \leq i \leq N$), taken modulo $\bmod 998244353$. Output in the following format.

$x_{1}$ $x_{2}$ $\cdots$ $x_{N}$

Sample

Sample 1
Input
6
1 1
2 1
3 1
4 1
6 1
8 1
Output
499122178
3 3
499122181 6 499122181
6 9 9 6
9 15 18 18 15 9
12 21 27 30 30 27 21 12

For the first test case, each time she teleports, Yukishii remains in the labyrinth with probability $1/3$ and escapes with probability $2/3$.
Rephrasing the expected number of monsters defeated before escaping the labyrinth when starting from room 1 in terms of the probability of still being in the labyrinth after defeating $i$ monsters, we obtain
$$ \sum_{i=0}^{\infty} \left(\frac{1}{3}\right)^{i} = \frac{1}{1 - \frac{1}{3}} = \frac{3}{2} $$ so we can see that the expected value is $\frac{3}{2}$ monsters. Since $3 \equiv 2 \times 499122178\,(\bmod 998244353)$, output 499122178.
For the second test case, whether she is in room 1 or room 2, a teleportation leaves her in the labyrinth with probability $2/3$ and lets her escape with probability $1/3$.
The expected number of monsters defeated before escaping the labyrinth is $$ \sum_{i=0}^{\infty} \left(\frac{2}{3}\right)^{i} = \frac{1}{1 - \frac{2}{3}} = 3 $$ .
For the third test case, the expected values are $\left[\frac{9}{2},\,6,\,\frac{9}{2}\right]$.

Sample 2
Input
9
1 2
2 2
3 2
4 2
7 2
7 3
7 4
7 5
7 20
Output
748683266
665496237 665496237
499122179 499122179 499122179
873463812 249561092 249561092 873463812
778043398 939524104 176160777 807403530 176160777 939524104 778043398
718952164 153160239 32433937 135141389 32433937 153160239 718952164
683009297 643604915 275830680 275830680 275830680 643604915 683009297
858490146 119789325 119789325 119789325 119789325 119789325 858490146
792723458 792723458 792723458 792723458 792723458 792723458 792723458

For the 1st test case, the expected values are $[\frac{5}{4}]$.
For the 2nd test case, the expected values are $[\frac{5}{3},\,\frac{5}{3}]$.
For the 3rd test case, the expected values are $[\frac{5}{2},\,\frac{5}{2},\,\frac{5}{2}]$.
For the 4th test case, the expected values are $[\frac{25}{8},\,\frac{15}{4},\frac{15}{4},\,\frac{25}{8}]$.
For the 5th test case, the expected values are $[\frac{355}{68},\,\frac{120}{17},\frac{150}{17},\,\frac{625}{68},\,\frac{150}{17},\,\frac{120}{17},\,\frac{355}{68}]$.
For the 6th test case, the expected values are $[\frac{2009}{554},\,\frac{2401}{554},\,\frac{1372}{277},\,\frac{3031}{554},\,\frac{1372}{277},\,\frac{2401}{554},\,\frac{2009}{554}]$.
For the 7th test case, the expected values are $[\frac{54}{19},\,\frac{243}{76},\,\frac{267}{76},\,\frac{267}{76},\,\frac{267}{76},\,\frac{243}{76},\,\frac{54}{19}]$.
For the 8th test case, the expected values are $[\frac{121}{50},\,\frac{66}{25},\,\frac{66}{25},\,\frac{66}{25},\,\frac{66}{25},\,\frac{66}{25},\,\frac{121}{50}]$.
For the 9th test case, the expected values are $[\frac{41}{34},\,\frac{41}{34},\,\frac{41}{34},\,\frac{41}{34},\,\frac{41}{34},\,\frac{41}{34},\,\frac{41}{34}]$.

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