D - Factorization

長さ $n$ の正整数の配列で、各要素の積が正整数 $m$ となるようなものが何通りなるか、という問題。

解法

$m$ の素因数分解を考え、 $m = p_1^{a_1}\ldots p_k^{a_k}$ とします。今の問題は次のように言い換えることができます。

$n$ 個の箱があり、 $a_i$ 個の $p_i$ を重複を許して入れます。それぞれの $p_i \ (1 \le i \le k)$ についてこの作業をする場合の、入れ方の場合の数はいくらか。

この言い換えが問題の本質です。たとえば $n = 3, m = 8$ としたときに[1,1,8]も[1,2,4]も[2,2,2]も全部今の方法でもれなく数え上げられていることを確認してみてください。

このときの場合の数は、 $i$ について独立に考えることができます。そこで以下の問題を考えます。

$n$ 個の箱があり、 $a$ 個の $p$ を重複を許して入れる場合の数はいくらか。

これは重複組合せの計算であり、 $dp[i][j] = i$ 番目までのアイテムから $j$ 個重複を許して入れる場合の数、とした動的計画法を考えることで解けます。