\(f_i\) をこれから合計 \(i\) 枚以上のレアカードを手に入れるまでに開封するパックの個数の期待値、\(g_i\) を \(1\) つのパックにレアカードがちょうど \(i\) 枚入っている確率とします。求める答えは \(f_X\) です。

\(f_i\) を dp の要領で求めます。\(i = 0\) のときは \(f_i = 0\) です。\(i > 0\) のときは次に開封するパックに入っているレアカードの枚数で場合分けして足し合わせることを考えることにより、\(f_i = 1 + \displaystyle\sum_{j = 0}^{N} f_{ \max(i - j, 0) }g_j\) がわかります。このままでは右辺に \(f_i\) を含む項が存在するため素朴な dp による計算が行えませんが、\(j = 0\) の項を移項することにより \(f_i(1 - g_0) =1 + \displaystyle\sum_{j = 1}^{N} f_{ \max(i - j, 0) }g_j\) が得られるので、\(f_i =\frac{1}{1 - g_0}(1 + \displaystyle\sum_{j = 1}^{N} f_{ \max(i - j, 0) }g_j)\) という式により \(i\) について昇順に \(f_i\) の値が計算できます。ここで、制約から \(g_0 \leq \frac{99}{100}\) であるため \(1 - g_0 \neq 0\) であることに注意してください。

したがって、\(g_j\) たちの値が求まっているとき、\(f_X\) の値は \(O(NX)\) 時間で計算できます。

以上により \(g_j\) たちの値を求めることに帰着できましたが、これも dp の要領で求めることができます。\(dp_ { i, j }\) を \(1, 2, \ldots, i\) 枚目にちょうど \(j\) 枚のレアカードがある確率とすると、\(i\) 枚目がレアカードであるかに着目してそれぞれの確率を足すことにより、\(dp_{ i,j } = \frac{ P_i }{100} dp_{ i - 1, j - 1 } + (1 - \frac{ P_i }{100})dp_ { i - 1, j }\) がわかります。 この dp は全体として \(O(N ^ 2)\) 時間で計算でき、\(g_j = dp_{ N, j }\) です。

以上より全体として \(O(NX + N ^ 2)\) 時間で解くことができます。