問題一覧 > 通常問題

No.3176 Teleportation Labyrinth (Hard)

レベル : / AI推定難易度 : 2175 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 11
作問者 : t98slider / テスター : akakimidori
お気に入りにしたユーザー ProblemId : 11959 / 自分の提出
問題文最終更新日: 2026-10-24 12:27:11
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 Easy version only in the size of the constraint on $N$.

Problem Statement

Yukishi has gotten lost in a teleportation labyrinth.
In the vicinity of the teleportation labyrinth (including the labyrinth itself), there exist rooms 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 Yukishi 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$.
  • Being in room $x$, she is teleported to room $x + d$.
    (Note that a teleportation from room $x$ to room $x$ is possible.)
Each time Yukishi teleports, the monsters are placed again, and she is considered to have escaped the teleportation labyrinth when she teleports to a room that is not one of room $1$ to room $N$.
For each case where Yukishi starts exploring from room $i$ ($1 \leq i \leq N$), find the expected number of monsters she must defeat before escaping the teleportation labyrinth, modulo $\bmod 998244353$. More precisely, when the expected value is expressed 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 2 \times 10^{5}$
  • $1 \leq K \leq 20$
  • The sum of $N$ over all test cases does not exceed $2 \times 10^{5}$.
  • All inputs are integers.

Input

The input is given from standard input in the following format. Here, $\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, taken $\bmod 998244353$, of monsters Yukishi must defeat before escaping the teleportation labyrinth when she starts exploring from room $i$ ($1 \leq i \leq N$). 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

In the first test case, at each teleportation Yukishi 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, starting from room 1, in terms of the probability of remaining 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} $$ and thus the expected value is $\frac{3}{2}$ monsters. Since $3 \equiv 2 \times 499122178\,(\bmod 998244353)$, output 499122178.
In 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 she escapes 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 $$ .
In 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

In the 1st test case, the expected values are $[\frac{5}{4}]$.
In the 2nd test case, the expected values are $[\frac{5}{3},\,\frac{5}{3}]$.
In the 3rd test case, the expected values are $[\frac{5}{2},\,\frac{5}{2},\,\frac{5}{2}]$.
In the 4th test case, the expected values are $[\frac{25}{8},\,\frac{15}{4},\frac{15}{4},\,\frac{25}{8}]$.
In 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}]$.
In 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}]$.
In 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}]$.
In 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}]$.
In 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もしくは右上の雲マークをクリックしてアカウントを作成してください。