まず \(\mathrm{O}(NM)\) の dp を考えます。\(dp[i] =\) マス \(i\) に止まることがある確率、と定義しましょう。ただし、マス \(N\) 以降に止まったらもう進まないものとし、落とし穴があるマスについては dp の値は \(0\) とします。すると、答えは \(\sum_{N \le i \le 2N} dp[i]\) となります。

この dp は分割統治 FFT というアルゴリズムで高速化することが出来ます。https://atcoder.jp/contests/abc213/editorial/2396 で詳しく解説がされていますが、ここは少し機械的に解説することにします。(リンク先には図解で丁寧に解説がなされているので分からない方はリンク先の解説をお読みください。)

\(f(i,j)\) を、マス \(i\) からマス \(j\) に \(1\) 回で移動することがあり得るならば \(dp[j]\) に \(\frac{dp[i]}{M}\) を加算する、という動作と定義します。(条件を満たさないならば何もしません。)

初期値として \(dp[0] = 1\) とし、\(f(i,j)(0 \le i < j \le 2N)\) を以下を満たすように実行することが出来れば dp 配列を得ることが出来ます。(\(2\) 個目の操作は \(f(i,j)\) の条件とは少し言い難いですが落とし穴を簡単に考慮するためこのようにします。)

• \(f(i,j)\) を実行するならば、\(f(k,i)(k < i)\) はすべて実行し終わっている。
• \(f(k,i)(k < i)\) を全て実行し終わったときに、マス \(i\) が落とし穴なら \(dp[i]\) に \(0\) を代入する。

通常の dp においては、\(i = 1,2,\dots,2N\) の順に \(k = 0,1,\dots,i-1\) について \(f(k,i)\) を行い、適時 \(dp[i]\) に \(0\) を代入するというものでこれは上の条件を満たしています。

ここで、\(f(i,j)\) の実行順序を工夫することで高速化をすることを考えます。例えば、\(a \le i \le b < j \le c\) を満たす \((i,j)\) 全てについて \(f(i,j)\) を行うことを考えます。これは畳み込みを用いて高速に行うことが出来ます。

\(f(x) = \sum_{i=a}^{\min(b,N-1)} dp[i]x^i,g(x) = \sum_{i=1}^{M} \frac{x^{A_i}}{M}\) とし、\(h(x) = f(x)g(x)\) を計算します。そして、\(b < j \le c\) を満たす \(j\) について \(dp[j]\) に \([x^j]h(x)\) を加算すればよいです。このままだと \(\mathrm{O}(c \log c)\) かかっていますが、\(f(x)\) の \(x^a\) 未満の項は要らないので切り落とし、\(g(x)\) の \(x^{c-a}\) 超過の項は要らないので切り落とすと \(\mathrm{O}((c-a) \log (c-a))\) で計算を行うことが出来ます。これは愚直に行った場合の \(\mathrm{O}((b-a)(c-b))\) に比べて多くの場合高速になっています。これを用いて元の問題も高速化しましょう。

\(solve(l,r)\) 関数を実行すると \(l \le i < j \le r\) を満たす \((i,j)\) について適切な順序で \(f(i,j)\) が実行されるものとします。この中身を以下のように実装します。

• \(l=r\) ならば \(f(i,l)(i < l)\) が全て実行し終わっているため、マス \(l\) が落とし穴なら \(dp[l] = 0\) として終了する。
• そうでないならば \(m=\frac{(l+r)}{2}\) として \(solve(l,m)\) を実行する。
• そして、上記のように \(l \le i \le m < j \le r\) を満たす \((i,j)\) について \(\mathrm{O}((r-l)\log (r-l))\) で \((i,j)\) を計算する。
• \(solve(m+1,r)\) を実行する。

このアルゴリズムが適切な順序で \(f(i,j)\) を行っていることが確認できます。計算量解析をすると、再帰の \(k\) 段目でかかる計算量の合計が \(\mathrm{O}(N \log N)\) となり、\(k\) は \(\mathrm{O}(\log N)\) となるため、全体で \(\mathrm{O}(N \log^2 N)\) で処理が完了していることが分かります。