前問の解法の計算量は$O(m^3\log n)$なので、本問のように$m$が大きい場合は使用できません。一方で、今回は前問に比べて$n$は小さいです。そこで、形式的冪級数を用います。

$x$についての多項式$f$の$x^k$の係数を$[x^k]f$と表すと、サイコロを$k$回振った時に点$n$に止まる確率は$[x^n]\left\{\frac{1}{m}x+\frac{1}{m}x^2+\cdots+\frac{1}{m}x^m\right\}^k$となります。よって、求める確率$p_n=\displaystyle\sum_{k=0}^{\infty}[x^n]\left\{\frac{1}{m}x+\frac{1}{m}x^2+\cdots+\frac{1}{m}x^m\right\}^k=[x^n]\displaystyle\sum_{k=0}^{\infty}\left\{\frac{1}{m}(x+x^2+\cdots+x^m)\right\}^k=[x^n]\displaystyle\frac{1}{1-\frac{1}{m}(x+x^2+\cdots+x^m)}=[x^n]\displaystyle\frac{m(1-x)}{m-(m+1)x+x^{m+1}}$となります。

この記事より、形式的冪級数の逆元は$O(n\log n)$で求めることができるので、全体の計算量は$O(n\log n)$となり、十分時間内に間に合います。

解答例

形式的冪級数の積を求める際にmod環上での畳み込みを行うため、AC Libraryの一部を引用しました。引用した部分に関しては、解答例にその旨を明記してあります。

質問・誤りがある場合

Twitterに連絡ください。ID : @YS55749378