No.3176 転移迷宮 (Hard)
タグ : / 解いたユーザー数 11
作問者 :
t98slider
/ テスター :
akakimidori
まえがき
Easy versionの問題とは $N$ に関する制約の大きさのみ異なります。
問題文
ユキシーは転移迷宮で遭難してしまいました。
転移迷宮付近 (転移迷宮自身を含む) には部屋 $-10^{100}$ ～ 部屋$10^{100}$ までの部屋が存在していて、転移迷宮には部屋 $1$ ～ 部屋 $N$ までの$N$ 個の部屋が割り当てられています。
転移迷宮内の $N$ 個の部屋にはそれぞれ $1$ 体ずつモンスターが配置されています。
ユキシーは部屋 $x$ ($1 \leq x \leq N$) を訪れるたびにモンスターと戦い、部屋 $x$ のモンスターを倒すと次の転移が発生します。
- $d$ を $-K \leq d \leq K$ を満たす $2K+1$ 個の整数の中から等確率に選択する。
- 部屋 $x$ にいるときに部屋 $x + d$ に転移する。
(部屋 $x$ から部屋 $x$ への転移がありうることに注意してください。)
ユキシーが部屋 $i$ ($1 \leq i \leq N$)から探索を開始した場合に、転移迷宮を脱出するまでに倒す必要のあるモンスターの数の期待値をそれぞれ $\bmod 998244353$ で求めてください。 より正確には、期待値が既約分数 $P/Q$ で表されるとき、 制約の範囲内において $R \times Q≡P (\bmod 998244353), 0 \leq R < 998244353$ を満たす整数 $R$ が一意に定まるので、その $R$ を出力してください。
制約
- $1 \leq N \leq 2 \times 10^{5}$
- $1 \leq K \leq 20$
- すべてのテストケースについての $N$ の総和が $2 \times 10^{5}$ を超えない。
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。ここで、$\mathrm{case}_i ~ (i = 1, 2, \cdots, T)$ は $i$ 個目のテストケースです。
$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$
各テストケースは以下の形式で与えられます。
$N$ $K$
出力
$T$ 行出力し、 $i$ 行目には $i$ 個目のテストケースについての答えを出力してください。
各テストケースについて、ユキシーが部屋 $i$ ($1 \leq i \leq N$)から探索を開始した場合の転移迷宮を脱出するまでに倒す必要のあるモンスターの数の期待値を$\bmod 998244343$としたものを $x_{i}$ とするとき、以下の形式で出力してください。
$x_{1}$ $x_{2}$ $\cdots$ $x_{N}$
サンプル
サンプル1
入力
6 1 1 2 1 3 1 4 1 6 1 8 1
出力
499122178 3 3 499122181 6 499122181 6 9 9 6 9 15 18 18 15 9 12 21 27 30 30 27 21 12
最初のテストケースについて、転移する度にユキシーは $1/3$ の確率で迷宮内に残り、 $2/3$ の確率で脱出します。
部屋1から開始し迷宮を脱出するまでに倒すモンスターの数の期待値をモンスターを $i$ 体倒したときに迷宮内に残っている確率に言い換えると、
$$
\sum_{i=0}^{\infty} \left(\frac{1}{3}\right)^{i} = \frac{1}{1 - \frac{1}{3}} = \frac{3}{2}
$$
が得られ、期待値は $\frac{3}{2}$ 体であることが分かります。$3 \equiv 2 \times 499122178\,(\bmod 998244353)$ なので499122178を出力します。
2番目のテストケースについては、部屋1にいる場合も部屋2にいる場合も転移によって$2/3$ の確率で迷宮内に残り、 $1/3$ の確率で脱出します。
迷宮を脱出するまでに倒すモンスターの数の期待値は
$$
\sum_{i=0}^{\infty} \left(\frac{2}{3}\right)^{i} = \frac{1}{1 - \frac{2}{3}} = 3
$$
となります。
3番目のテストケースについては、$\left[\frac{9}{2},\,6,\,\frac{9}{2}\right]$ が期待値になります。
サンプル2
入力
9 1 2 2 2 3 2 4 2 7 2 7 3 7 4 7 5 7 20
出力
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
1つめのテストケースについて $[\frac{5}{4}]$ が期待値になります。
2つめのテストケースについて $[\frac{5}{3},\,\frac{5}{3}]$ が期待値になります。
3つめのテストケースについて $[\frac{5}{2},\,\frac{5}{2},\,\frac{5}{2}]$ が期待値になります。
4つめのテストケースについて $[\frac{25}{8},\,\frac{15}{4},\frac{15}{4},\,\frac{25}{8}]$ が期待値になります。
5つめのテストケースについて $[\frac{355}{68},\,\frac{120}{17},\frac{150}{17},\,\frac{625}{68},\,\frac{150}{17},\,\frac{120}{17},\,\frac{355}{68}]$ が期待値になります。
6つめのテストケースについて $[\frac{2009}{554},\,\frac{2401}{554},\,\frac{1372}{277},\,\frac{3031}{554},\,\frac{1372}{277},\,\frac{2401}{554},\,\frac{2009}{554}]$ が期待値になります。
7つめのテストケースについて $[\frac{54}{19},\,\frac{243}{76},\,\frac{267}{76},\,\frac{267}{76},\,\frac{267}{76},\,\frac{243}{76},\,\frac{54}{19}]$ が期待値になります。
8つめのテストケースについて $[\frac{121}{50},\,\frac{66}{25},\,\frac{66}{25},\,\frac{66}{25},\,\frac{66}{25},\,\frac{66}{25},\,\frac{121}{50}]$ が期待値になります。
9つめのテストケースについて $[\frac{41}{34},\,\frac{41}{34},\,\frac{41}{34},\,\frac{41}{34},\,\frac{41}{34},\,\frac{41}{34},\,\frac{41}{34}]$ が期待値になります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。