振り終わったサイコロからいくつかのサイコロを選んで、選んだサイコロの出目の総和が \(k\) になるようにできることを、単に \(k\) を作れるということにします。

動的計画法（いわゆる bit DP ）で本問題を解きます。 \(N\) 個のサイコロを同時に振る代わりに、\(1\) 番目のサイコロから順に \(1\) 個ずつ振ることにし、各サイコロを振り終わった時点での作れる整数の集合を考えます。本問題では最終的に \(10\) が作れるかが問題なので、\(10\) 以下の整数についてのみ関心があります。 そこで、DP テーブルを

\(\mathrm{dp}[i][S] = \) （ \(1, 2, \ldots, i\) 番目のサイコロを振り終わった時点で、作れる \(10\) 以下の整数の集合が \(S\) である確率）

とおきます。 この DP テーブルを埋めることで、本問題の答えが

\[\sum_{S \owns 10} \mathrm{dp}[N][S]\]

として得られます。

まず、DP の初期化を考えます。 最初の時点では、\(0\) 個のサイコロを振り終わっており、作れる整数は \(0\) のみ（振り終わった \(0\) 個のサイコロの中から \(0\) 個の出目を選ぶ）ですので、

\[ \mathrm{dp}[0][S] = \begin{cases} 1 &\,\,\text{if}\,\, S = \lbrace 0 \rbrace \\ 0 &\,\,\text{if}\,\, S \neq \lbrace 0 \rbrace \end{cases} \]

です。

次に、DP の遷移を考えます。 現在 \(i\) 番目のサイコロまで振り終わっており、作れる \(10\) 以下の整数の集合が \(S\) である状態を考えます。 \(i+1\) 番目のサイコロを振った結果その出目が \(x\) だったとすると、 この新たな出目を含めた \(i+1\) 番目の出目までで作れる \(10\) 以下の整数の集合は、

• 新しい出目 \(x\) を選ばない場合に作れるものの集合 （ \(i\) 番目までの出目で元々作れるものの集合 \(S\) に等しい）と、
• 新しい出目 \(x\) を選ぶ場合に作れるものの集合 （ \(i\) 番目の出目までで元々作れた \(s \in S\) に新たな出目 \(x\) を加えた \(s+x\) が作れるため \(T_x \coloneqq \lbrace s + x : s \in S \rbrace \cap \{0, 1, 2, \ldots, 10\}\) に等しい）

の和集合 \(S \cup T_x\) になります。

\(i+1\) 番目のサイコロの出目 \(x\) は、\(1, 2, \ldots, A_{i+1}\) のいずれかを等しく \(1 / A_{i+1}\) の確率でとるので、\(A_{i+1} \leq 10\) のときは

• \(x = 1\) の場合に対応して、\(\mathrm{dp}[i+1][S \cup T_1]\) に \(\mathrm{dp}[i][S] \times (1 / A_{i+1})\) を加算、
• \(x = 2\) の場合に対応して、\(\mathrm{dp}[i+1][S \cup T_2]\) に \(\mathrm{dp}[i][S] \times (1 / A_{i+1})\) を加算、
• \(\cdots\)
• \(x = A_{i+1}\) の場合に対応して、\(\mathrm{dp}[i+1][S \cup T_{A_{i+1}}]\) に \(\mathrm{dp}[i][S] \times (1 / A_{i+1})\) を加算

という \(A_{i+1}\) 本の遷移をすれば良いです。

また \(A_{i+1} \gt 10\) のときは、「 \(x \gt 10\) ならば \(T_x = \emptyset\) 」が成り立つことを用いると \(x \gt 10\) の場合に対応する遷移は \(1\) 本にまとめることができ、具体的には、

• \(x = 1\) の場合に対応して、\(\mathrm{dp}[i+1][S \cup T_1]\) に \(\mathrm{dp}[i][S] \times (1 / A_{i+1})\) を加算、
• \(x = 2\) の場合に対応して、\(\mathrm{dp}[i+1][S \cup T_2]\) に \(\mathrm{dp}[i][S] \times (1 / A_{i+1})\) を加算、
• \(\cdots\)
• \(x = 10\) の場合に対応して、\(\mathrm{dp}[i+1][S \cup T_{10}]\) に \(\mathrm{dp}[i][S] \times (1 / A_{i+1})\) を加算、
• \(11 \leq x \leq A_{i+1}\) の場合に対応して、\(\mathrm{dp}[i+1][S]\) に \(\mathrm{dp}[i][S] \times ((A_{i+1}-10) / A_{i+1})\) を加算、

という \(11\) 本の遷移をすれば良いです。

\(S \subseteq \lbrace 0, 1, 2, \ldots, 10 \rbrace\) より、\(S\) としてあり得るのは高々 \(2^{11} = 2048\) 通りであるため、 DP テーブルの状態数として \(2048N \leq 204800\) 通りを考えればよく、各状態からの遷移は高々 \(11\) 本ですので、DP テーブルを埋めて本問題の答えを得ることが十分高速に可能です。