No.3176 Teleportation Labyrinth (Hard)
タグ : / 解いたユーザー数 11
作問者 :
akakimidori
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.)
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もしくは右上の雲マークをクリックしてアカウントを作成してください。