D - Idol Group Costume 解説 by Mitsubachi


方針は公式解説と大体同じです. $M$ が昇順とします. $dp[i][j]$ を $i$ 人目までで $j$ 人選んで, $j$ 人目までの服装が一致している確率とすると,初期値と遷移は以下の通りです.

  • $dp[0][0] = 1$
  • $dp[i+1][0] \leftarrow dp[i+1][0] + dp[i][0]$
  • $dp[i+1][1] \leftarrow dp[i+1][1] + dp[i][0]$
  • $dp[i+1][j] \leftarrow dp[i+1][j] + dp[i][j]$ $(1 \leq j)$
  • $dp[i+1][j+1] \leftarrow dp[i+1][j+1] + \frac{1}{M_j} dp[i][j]$ $(1 \leq j)$
答えは $dp[N][K]$ を ${}_{N}C_{K}$ で割ったものです.このまま書くと $O(N^2)$ なので高速化します.

多項式 \(f_i\)\(\sum_{1 \leq j} dp[i][j] x^j\) とします.すると, DP の遷移は \(f_{i+1} = x + \left( 1 + \frac{1}{M_j} x \right) f_i\) と書けます. これは, \(\begin{pmatrix} 1 \\ f_{i+1} \\ \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ x & 1 + \frac{1}{M_j} x \\ \end{pmatrix} \begin{pmatrix} 1 \\ f_i \\ \end{pmatrix}\) と書き直せます.

よって,この遷移行列の積を取れば良いです. queue に入れていく方針もありますが,公式解説のように抽象化セグメント木を使うと行列間の順序を気にせずに解けます.

投稿日時:
最終更新: