This is my first codeforces blog :) Please forgive me for my poor English lol

For this problem, first we can write a recurrence: $$$ dp_{i, j} = \sum_{d | j} dp_{i - 1, d} $$$ where $$$ i $$$ stands for the length for the sequence now and $$$ j $$$ stands for the last element of the sequence (or $$$ A_i $$$). And we need to calculate $$$ \sum_{1 \leq i \leq m} dp_{n, i} $$$.

Initially, $$$ dp_{1, j} = 1 $$$, and it's obvious.

Actually, we can rewrite the recurrence if we let $$$ f_{i}(j) = dp_{i, j} $$$, the recurrence can be presented as a dirichlet convolution: $$$ f_{i} = f_{i - 1} * 1 $$$, and $$$ f_1 = 1 $$$.

This leads us to a useful conclusion: $$$ f_i $$$ is a multiplicative function. Because $$$ f_1 = 1 $$$ is a multiplicative function, and the dirichlet convolution of two multiplicative functions is also a multiplicative function, we get this immediately.

After some observation, we can get $$$ f_n(1) = 1 $$$ and $$$ f_n(p ^ k) = \binom{n - 1 + k}{k} $$$. (the proof will be written soon)

Using the above facts, we can solve the problem with the problem with a linear sieve, the procedure is quite similar to the calculation of $$$ d(n) = \sum_{i | n} 1 $$$.

Calculate the inversions first, and the solution can be implemented in $$$ O(m) $$$ time and $$$ O(m) $$$ space, which is irrelevant with $$$ n $$$.

Code

The official solution is published soon, the only difference is that i use a linear sieve to solve the problem