I've been trying to do this question since many hours and am unable to visualize the authors solution. The question involves maintaining a 1d dp from a 2d dp.

I'm unable to understand what does dp[j] represent in the authors solution after ignoring (i) from dp states ?

It's not a very clear tutorial, in fairness.

The idea is that you have an array of counts (cnt in the author's solution), which after 0 indices has cnt[0] = 1, and cnt[x] = 0 for all other x (up to 10^6). You iterate through each index of the array a, and update the cnt array each time (this is like the first dimension of the DP, except that you aren't storing all the old cnt arrays, you're just updating the new one, to avoid MLE). The second dimension of the DP is handled by looking at all the factors of a[i], and these are stored in a temporary vector (cur). At the end of each iteration, cur is used to update all of the indices of cnt which could possibly have changed, thus avoiding iterating through every index and risking a TLE.

while updating the dp[j] why do we need to iterate through the divisors(j) in the descending order?

The reason for that is that when we have a factor j, and we need to update

`cnt[j]`

, we must add to j the value of`cnt[j-1]`

from the previous iterationsince we effectively want to do`dp[i][j] += dp[i-1][j-1]`

. By iterating in descending order, we ensure that we have`dp[i-1][j-1]`

, not`dp[i][j]`

The basic idea is that $$$dp_{i}$$$ = # of good subsequences of length $$$i$$$. Then you can iterate through the array, find all of the divisors of $$$a[i]$$$ and then update the answer accordingly. Don't forget to increase $$$dp[1]$$$ after each iteration! My code: https://codeforces.com/contest/1061/submission/104371163