ARC116 C - Multiple Sequences (500)
コンテスト中の考察
$ dp[i][j] としてi番目まで見たときに最後の値がjの時の場合の数とすると、遷移が仮に$ O(1)でも$ O(NM)になりTLEになる
整数列の最後の値になるまでどこで増えるかを管理することになりそう
区切り位置としてあり得るものを組み合わせから求めるやつ
ある素数について分かれて使われる場合と一緒に使われる場合の数をうまく計算できない
解説の方法
素因数毎に考えると素因数毎の結果は他の素因数の結果と独立になるので単純に積を求めれば良い
ある素因数を$ x個含む場合、その素因数での配置のパターンは$ _{x+n-1}C_{n-1}
組み合わせは事前に$ O(N)で求めると後で$ O(1)で利用できる
素因数分解のパートは$ O(M^{\frac{3}{2}})
全体では$ O(N+M^{\frac{3}{2}})