He is only in grade 9 ;)

In Round 752 (right now), he ranked 14th and will gain +104 rating, then, become the youngest LGM (even younger than djq_cpp)


Congratulations!

In my perspective, recent div.1 contests (maybe also include div.2) are much harder than before in codeforces.

In round 743 (div.1), problem A is only 1800 while problem B is 2500, then C is 2700, such a huge gap.

In round 745 (div.1), problem A is 1700, problem C is 2200 while problem B is 2600 and problem D is 2900.

If you participate in (or virtual participate in) these two contests, I think you must agree that they're much harder than previous contests. I don't think it's a coincidence, though problems are always getting harder though time lol

On AtCoder, ARC has returned and ABC has added more problems which means the difficulty is increased.

So maybe codeforces are started to change? I think now the difficulty of div.1 is more close to AGC, but I'm no so sure.

I'm glad to hear your ideas ^_^

btw, i hope someone could tell me some methods to train to deal with recent problems, they're hard and focus more on thinking which i'm not so used to ;)

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