計算量は劣りますが、発想実装共に容易な \(O\left(M\log ^2M\right)\) を説明します。

自然な動的計画法として、以下のようなものが挙げられます。

\(DP[i][j] = \) 積が \(i\) となるような長さ \(j\) の列の個数

として、

\(\displaystyle DP[i][j + 1] = \sum_{k | i} DP[k][j]\)

と計算できます。 (\(k|i\) は \(k\) は \(i\) の正の約数という意味)

この動的計画法は、調和級数による評価により全体で \(O\left(MN log M\right)\) となっていることがわかります。

この動的計画法を高速化することを考えます。 \(i\) を削るのは難しそうなので、\(j\) を削ることを考えます。 \(j\) が大きい時を考えると、\(2\) 以上の整数は列の中に高々 \(\lceil log_2 M \rceil\) 個であることから、ほとんどが \(1\) であることがわかります。すると、 \(1\) を抜いて DP を計算すると十分高速になることがわかります。

最後に \(j\) 個を \(N\) 個のうちどこに位置を保って配置するかを考えればよいです。(残りは \(1\) で埋める。) これは \(DP[i][j]\) に対して \(_NC_j\) を掛け算すればよいです。

計算量は \(O\left(M log ^2 M + N \right)\) です。

\(AC\) コード

(C++)[https://atcoder.jp/contests/arc116/submissions/21382961]

(pypy3)[https://atcoder.jp/contests/arc116/submissions/21383316]