D - Factorization
D - Factorization
長さの正整数の配列で、各要素の積が正整数となるようなものが何通りなるか、という問題。
解法
の素因数分解を考え、とします。今の問題は次のように言い換えることができます。
個の箱があり、個のを重複を許して入れます。 それぞれのについてこの作業をする場合の、入れ方の場合の数はいくらか。
この言い換えが問題の本質です。たとえばとしたときに[1,1,8]も[1,2,4]も[2,2,2]も全部今の方法でもれなく数え上げられていることを確認してみてください。
このときの場合の数は、について独立に考えることができます。そこで以下の問題を考えます。
個の箱があり、個のを重複を許して入れる場合の数はいくらか。
これは重複組合せの計算であり、番目までのアイテムから個重複を許して入れる場合の数、とした動的計画法を考えることで解けます。