### dblark's blog

By dblark, 2 years ago, 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  Comments (0)
| Write comment?