The optimal sequence of operations is very simple.

The optimal sequence of operations is adding $$$k-1$$$ 1-s into the set each time, at the same time decreasing $$$n$$$ by $$$k-1$$$. This implies that the answer is $$$\lceil \frac{n-1}{k-1}\rceil$$$.

"Most sequences" can be transformed into $$$[1]$$$. Conditions for a sequence to be un-transformable is stringent.

Find several simple substrings that make the string transformable.

We list some simple conditions for a string to be transformable:

• If 111 exists somewhere (as a substring) in the string, the string is always transformable.
• If 11 appears at least twice in the string, the string is always transformable.
• If the string both begins and ends with 1, it is always transformable.
• If the string begins or ends with 1 and 11 exists in the string, it is always transformable.

These can be found by simulating the operation for short strings on paper.

Contrarily, if a string does not meet any of the four items, it is always not transformable. This can be proved using induction (as an exercise).

Formulate the problem.

Some variables can't be large.

Suppose monster $$$i$$$ is killed in round $$$b_i$$$. Then, the total health decrement is the sum of $$$a_i\times b_i$$$. The "independent set" constraint means that for adjacent vertices, their $$$b$$$-s must be different.

Observation: $$$b_i$$$ does not exceed $$$\lfloor \log_2 n\rfloor+1$$$. In this problem, $$$b_i\le 19$$$ always holds for at least one optimal $$$a_i$$$.

By dp, we can find the answer in $$$O(n\log n)$$$ or $$$O(n\log^2 n)$$$, depending on whether you use prefix/suffix maximums to optimize the taking max part.

Bonus: Find a counterexample for $$$b_i\le 18$$$ when $$$n=300000$$$. (Pretest 2 is one case)

Formulate the problem on a cartesian tree.

We can use dp to calculate the number of permutations of $$$1\sim n$$$ with $$$i$$$ prefix maximums and $$$j$$$ ascents, $$$f(n,i,j)$$$: consider where 1 is inserted, we have

For suffix maximums, (the number of permutations of $$$1\sim n$$$ with $$$i$$$ prefix maximums and $$$j$$$ ascents, $$$g(n,i,j)$$$, we can just reverse some dimension of $$$f$$$).

This runs in $$$O(n^3)$$$.

To calculate the answer, consider the position of $$$n$$$. Suppose it's $$$p$$$. The the answer is

Let $$$u(x,y)=\sum_{i}f(x,i,y)a_{i+1}$$$, $$$v(x,y)=\sum_{z}g(x,i,y)b_{i+1}$$$ (both of these are calculated in $$$O(n^3)$$$), then the answer is

This solves this easy version. FFT can speed the calculation up to $$$O(n^2\log n)$$$ per $$$n$$$, but the modulo number is bad.

To solve the hard version, we still need to consider $$$u(p-1,*)$$$ and $$$v(n-p,*)$$$ as polynomials $$$\sum_{i}u(p-1,i)x^i,\sum_{i}v(n-p,i)x^i$$$. Instead of doing FFT, consider substitute $$$x$$$ with $$$0,1,\dots,n+1$$$, and use interpolation to recover the final coefficients.

Suppose we have a value of $$$x$$$. Then, calculating $$$u(p-1)$$$ and $$$v(n-p)$$$ takes $$$O(n^2)$$$ in total. For fixed $$$x$$$ and $$$n$$$, the answer for $$$n$$$ is (here, note how $$$x$$$ is multiplied)

This also takes $$$O(n^2)$$$ in total. So, for each $$$x$$$, the calculation is $$$O(n^2)$$$.

For each $$$n$$$, the naive implementation of interpolation runs in $$$O(n^2)$$$. After we recover the coefficients, we multiply it with $$$c$$$ and update the answer.

So, the time complexity is $$$O(n^3)$$$.