問題概要

Problem - C - Codeforces

数列 $a$ が与えられ、数列 $a$ から0個以上の要素を取り除いた数列を数列 $b$ という。
数列 $b$ の要素が1つ以上あり各 $b_i$ が $i$ $( 1 \leq i \leq |b| )$ で割り切れる時、数列 $b$ を数列 $a$ の良い部分列と呼ぶ。
数列 $a$ の良い部分列の総数を10⁹+7で割った余りを求める。

制約

1 $\leq$ $N$ $\leq$ 10⁵
1 $\leq$ $a_i$ $\leq$ 10⁶

考えたこと

解説ACをしたのでこれCodeforces Round #523 Editorial - Codeforcesと同じことをしました。

まず、「 $dp[ i ][ j ]$ ：＝ $a_i$ まで見たときに $j$ 個で構成される良い部分列の数」というDPを考える。遷移は以下のようになり、 $\sum_{i=1}^n dp[ n ][ i ]$ が答えになるが制約的に二次元配列ではもてない。

${}$ $$ dp[ i ][ j ]= \left\{ \begin{array}{} dp[ i-1 ][ j ] + dp[ i-1 ][ j-1 ] & ( a_i が j で割り切れる時) \\ dp[ i-1 ][ j ] & (上以外の時) \end{array} \right. $$

Editorialには $dp[i]$ は $dp[i-1]$ にのみ依存するから1次元でもうまくいくよ！みたいに書いてあったがこれでは納得ができなかった。
参加者のコメントを参考に考えた結果、「 $dp[ i ]$ ：＝ $i$ 個で構成される良い部分列の数」というDPを考えるとする。例えば $a_i=6$ の時、 $6$ の約数は ${1,2,3,6}$ なので $a_i$ は数列 $b$ の1番目、2番目、3番目、6番目に置くことができるのはわかる。なので $a_i$ の約数 $x_i$ を降順に $dp[x_j]+=dp[x_j-1]$ のように更新していけばいいことになる。昇順に更新していった場合、 $a_i=6$ の例で言えば1番目に $a_i$ を使ったのに2番目でも $a_i$ を使うといったことが起きてしまうため正しくないことがわかる。