FPS24 J - スゴロク

考え方

計算量が $O(N^2)$ でよければ、各マスに止まる確率を持つ動的計画法で解ける。
これはABCでいうD問題レベルなので解説を省略する。

そして、これは分割統治による畳み込みで高速化できる。
「形式的冪級数」の記事参照。

今回は、ゴールで出目が余ってもよいという条件に工夫が必要。
余るときには出目を少なく見積もるというのは難しい。
そこで、すごろくの長さを $2N$ にし、本来のゴール以降はどこに止まってもゴールとする。
ゴールマスでは、そこに止まる確率をゴール確率に加算してから落とし穴に落とすことにすればよい。

計算量は $O(N\log^2 N)$ である。

具体例での動作

入力を受け取る。

n: 4
m: 3
l: 1
a: {1, 2, 3}
b: {3}

サイコロの出目は $1,2,3$ がそれぞれ確率 $\dfrac{1}{3}$ で、マス $3$ が落とし穴である。

まず、すごろくの長さを $2N=8$ にする。
今回は $8$ が既に $2$ の累乗なので、そのまま長さ $8$ のDPテーブルを用意する。
一般には、分割統治による畳み込みを行いやすくするため、$2N$ 以上の最小の $2$ の累乗までDPテーブルを用意する。

$dp_i$ をマス $i$ にいる確率とする。
また、$f_k$ を $k$ マス先へ進む確率を表す数列とする。
この例では、以下である。
$$
\{f_k\}=0,\dfrac{1}{3},\dfrac{1}{3},\dfrac{1}{3},0,0,\dots
$$

最初は $dp_0=1$、それ以外は $0$ とする。

まず、マス $0$ からマス $1$ への遷移を処理する。
$$
dp_1=dp_0f_1=\dfrac{1}{3}
$$

これでマス $1$ より前からの遷移は全て反映されたので、マス $1$ の処理を行う。
マス $1$ は落とし穴でもゴールでもないので、そのままにする。

次に、マス $0,1$ からマス $2,3$ への遷移をまとめて畳み込みで処理する。
$(dp_0+dp_1x)$ と $\sum f_kx^k$ の畳み込みのうち、$x^2,x^3$ の係数を利用する。
$$
\begin{aligned}
dp_2&=dp_0f_2+dp_1f_1=\dfrac{4}{9}\\
dp_3&=dp_0f_3+dp_1f_2=\dfrac{4}{9}
\end{aligned}
$$

この時点でマス $2$ より前からの遷移は全て反映されたので、マス $2$ の処理を行う。
マス $2$ は落とし穴でもゴールでもないので、そのままにする。

次に、マス $2$ からマス $3$ への遷移を処理する。
$$
dp_3=\dfrac{4}{9}+dp_2f_1=\dfrac{16}{27}
$$

これでマス $3$ より前の全マスからマス $3$ への遷移が終わった。
マス $3$ は落とし穴なので、ここで $dp_3=0$ とする。

次に、マス $0,1,2,3$ からマス $4,5,6,7$ への遷移をまとめて処理する。
$(dp_0+dp_1x+dp_2x^2+dp_3x^3)$ と $\sum f_kx^k$ の畳み込みのうち、$x^4$ 以降の係数を利用する。
マス $3$ の値は既に $0$ なので、落とし穴から先へ遷移することはない。

ゴール以降で非零になる値は以下。
$$
\begin{aligned}
dp_4&=dp_1f_3+dp_2f_2+dp_3f_1=\dfrac{7}{27}\\
dp_5&=dp_2f_3+dp_3f_2=\dfrac{4}{27}
\end{aligned}
$$

本来のゴールはマス $4$ なので、マス $4$ 以降に止まる確率は勝つ確率に加える。
また、ゴール後にさらにサイコロを振ることはないので、勝つ確率に加えた後の値は $0$ にする。

まずマス $4$ の $\dfrac{7}{27}$ を勝つ確率に加え、$dp_4=0$ とする。

続いてマス $5$ の $\dfrac{4}{27}$ も勝つ確率に加え、$dp_5=0$ とする。

したがって、勝つ確率は以下になる。
$$
\dfrac{7}{27}+\dfrac{4}{27}=\dfrac{11}{27}
$$

これを $998244353$ で割った余りにすると、以下になる。
$$
\dfrac{11}{27}\equiv 295776105 \pmod{998244353}
$$

注意点

確率 $\dfrac{1}{M}$ は、$998244353$ 上では $M$ の逆元として扱う。
逆元は繰り返し二乗法で求める。

別解

特になし。