Subtask 1

For the first subtask, some very naive brute force will work. Each bucket will be poured into at most ~M~ times, and there are ~N~ of them, so there are ~N^M~ possible combinations, each taking ~N~ operations to check.

Time Complexity: ~\mathcal O(QN^{M+1})~

Subtask 2

For the second subtask, note that if we have three consecutive buckets, and the first is poured into ~a~ times and the second ~b~ times, then we must pour into the third one ~c = M - bK - a~ times. We can thus brute force all possibilities for the first two values of the answer array, and use this formula to get the remaining ones. If any values are negative or larger than ~M~, we don't have a solution.

Time Complexity: ~\mathcal O(QNM^2)~

Subtask 3

Note first that if ~NM~ is not divisible by ~K + 2~, we do not have a solution.

Furthermore, note that if ~M~ is divisible by ~K + 2~, a possible solution is ~\frac{M}{K + 2}~, repeated ~N~ times.

For the remainder of this editorial, let ~A_i~ be our answer array, where ~A_1~ is the amount we pour into the first bucket, and ~A_i~ is the amount we pour into the ~i~th bucket.

In fact, our buckets are in a circle, so let's make ~A~ infinite in both directions, where we have ~A_i = A_{i + N}~.

Now, let ~a, b, c, d~ be arbitrary consecutive elements of ~a~.

Note that we must have ~a + bK + c = M~, as mentioned in subtask 2.

For this subtask, if ~K = 1~, we have:

$$\displaystyle a + b + c = M$$ $$\displaystyle b + c + d = M$$

Or:

$$\displaystyle a - d = 0$$ $$\displaystyle a = d$$

So every third element is equal.

It should be clear that if every third element is equal, unless ~N~ is divisible by ~3~, ~A_i = A_{i + 1}~ (that is, all elements are equal).

If ~N~ is not divisible by ~3~, then we must have a solution with all identical elements, or no solution at all.

If ~N~ is divisible by ~3~, the following pattern yields the lexicographically smallest solution:

$$\displaystyle 0, 0, M, 0, 0, M, 0, \dots$$

And this is all that is required for the ~K = 1~ subtask.

Time Complexity: ~\mathcal O(QN)~

Subtask 4

For this subtask, we consider ~K = 2~. We now have:

$$\displaystyle a + 2b + c = M$$ $$\displaystyle b + 2c + d = M$$

So we have:

$$\displaystyle a + b - c - d = 0$$ $$\displaystyle a + b = c + d$$

If ~N~ is odd, we have:

$$\displaystyle A_i + A_{i + 1} = A_{i + 2} + A_{i + 3} = A_{i + N - 1} + A_{i + N} = A_{i - 1} + A_i$$

Or:

$$\displaystyle A_{i + 1} = A_{i - 1}$$

So every other element is equal. In fact, if ~N~ is odd:

$$\displaystyle A_i = A_{i + 2} = A_{i + N + 1} = A_{i + 1}$$

So every element is equal. This case proceeds similarly to the ~K = 1~ case mentioned above.

However, if ~N~ is even, the case proceeds differently. Let ~X = a + b~. Then:

$$\displaystyle \sum_{i = 1}^N A_i = A_1 + A_2 + \dots + A_N = \frac{N}{2} \times X$$

Also, let ~Y = b + c~. Then:

$$\displaystyle \sum_{i = 1}^N A_i = A_1 + A_2 + \dots + A_N = A_2 + A_3 + \dots + A_{N + 1} = \frac{N}{2} \times Y$$

So ~X = Y~, or ~a + b = b + c~, or ~a = c~.

So every other element is equal. Then:

$$\displaystyle a + 2b + c = M$$ $$\displaystyle 2a + 2b = M$$

So ~M~ must be even in order for a solution to exist.

In fact, our lexicographically smallest pattern is:

$$\displaystyle 0, \frac{M}{2}, 0, \frac{M}{2}, 0, \dots$$

This concludes the ~K = 2~ case.

Time Complexity: ~\mathcal O(QN)~

Subtask 5

For this subtask, we have ~K \ge 3~. We have:

$$\displaystyle a + bK + c = M$$ $$\displaystyle b + cK + d = M$$

Or:

$$\displaystyle a - b + (b - c)K + (c - d) = 0$$ $$\displaystyle (b - c)(K - 1) = d - a$$

Without loss of generality, assume ~b \ge c~, since if ~b < c~, we can consider the array backward.

Then, since ~K > 2~:

$$\displaystyle 1 < K - 1$$ $$\displaystyle (b - c) \le (K - 1)(b - c) = (d - a)$$

We have equality only when ~b = c~. Assume that ~b > c~. Then:

$$\displaystyle (b - c) < (d - a)$$ $$\displaystyle a + b < c + d$$

This means that:

$$\displaystyle A_i + A_{i + 1} < A_{i + 2} + A_{i + 3} < A_{i + 4} + A_{i + 5} < \dots$$

However, this means:

$$\displaystyle A_i + A_{i + 1} < A_{i + 2N} + A_{i + 2N + 1} = A_i + A_{i + 1}$$

Which is a contradiction.

Thus, we must have ~b = c~, which tells us that every element of the array must be equal.

In fact, when ~K > 2~, we have a solution if and only if ~M~ is divisible by ~K + 2~.

Time Complexity: ~\mathcal O(QN)~

Subtask 6

To finish off the solution, we need help from a little math.

Suppose our answer contains a repeating cycle ~C~ of length ~L~. Note that for this problem, ~L \le 3~. Let ~Y = \frac{N}{L}~, and note that it must be an integer. Then we need to compute:

$$\displaystyle \sum_{i = 1}^N A_i \times B^{i - 1} = \sum_{i = 1}^Y \sum_{j = 1}^L C_j \times B^{L(i - 1) + (j - 1)}$$ $$\displaystyle \sum_{i = 1}^Y (B^L)^{i - 1} \sum_{j = 1}C_j \times B^{j - 1}$$

Note that this inner sum can be precomputed. Assign it the value ~Z~:

$$\displaystyle \sum_{i = 1}^Y Z \times (B^L)^{i - 1}$$

This should look very similar to the geometric sequence formula, and we can apply it here:

$$\displaystyle Z \times \frac{\left(B^L\right)^Y - 1}{B^L - 1}$$

Note that since we are computing our answer modulo ~10^9 + 7~, instead of dividing, we need to multiply by the multiplicative modular inverse.

Time Complexity: ~\mathcal O(Q \log N)~

Final Thoughts

Although this problem has an (admittedly exhausting) proof, this problem should teach you to try solutions. Many who solved this problem attempted submitting ~\frac{M}{K + 2}~ ~N~ times and got AC on the ~K \ge 3~ case, and proceeded from there. The other way to approach this is bottom up; look at the subtasks and solve them individually, and then combine them together.

This problem isn't meant for you to sit and stare at for hours. Don't be afraid to guess.