DMOPC '20 Contest 3 P3 - A Ring of Buckets

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem types

Lily has a ring of N buckets, numbered from 1 to N. Each bucket has capacity M. She has a pouring bucket with capacity K + 2, and wants to fill all buckets completely without any overflow, that is, to M exactly. Unfortunately, every time she tries to pour into a bucket, she spills a little, and 1 unit is spilled into each adjacent bucket, with K poured into her original bucket. Note that 1 and N are adjacent.

Lily wants to fill all of the buckets to capacity, but wants to have zero overflow. Being a genius, Lily already knows the answer, and challenges you to find it too.

However, Lily will quickly bore of you listing out the N numbers, so she decides on the following formula. If A_i is the number of times you must pour into the ith bucket, Lily will choose an arbitrary number B and ask you to compute A_1 + A_2 \times B + A_3 \times B^2 + \ldots + A_N \times B^{N - 1}. This number may be large, so Lily will be satisfied if you can output it modulo 10^9 + 7. Additionally, if there are multiple solutions, choose the one that has the lexicographically smallest value of A_1, A_2, \ldots, A_N.

Finally, Lily has a lot of buckets, so she will ask you Q questions, each with their own values of N, M, K and B. Can you answer them all?


For all subtasks:

1 \le M,K \le 10^9

2 \le B \le 10^9

3 \le N \le 10^9

1 \le Q \le 10^4

Subtask 1 [1/15]

Q = 1

N,M,K \le 5

Subtask 2 [2/15]

Q = 1

N,M,K \le 400

Subtask 3 [3/15]

Q = 1

K = 1

1 \le N,M \le 10^6

Subtask 4 [3/15]

Q = 1

K = 2

1 \le N,M \le 10^6

Subtask 5 [3/15]

Q = 1

3 \le K \le 10^6

1 \le N,M \le 10^6

Subtask 6 [3/15]

No additional constraints.

Input Specification

The first line will contain Q, the number of questions.

The next Q lines will contain four integers each, N,M,K,B.

Output Specification

Output Q lines. For each question, if it is impossible to fill all the buckets exactly to capacity, output -1.

Otherwise, output the required integer as specified above. Don't forget to output it modulo 10^9 + 7.

Sample Input 1

4 4 1 100

Sample Output 1


Explanation for Sample Output 1

There is no way to fill all the buckets exactly.

Sample Input 2

3 4 2 7

Sample Output 2


Explanation for Sample Output 2

If we pour once into each bucket, we get a solution array 1 1 1. Then, our required value is:

\displaystyle 1 + 1 \times 7 + 1 \times 7^2 = 57

Sample Input 3

999999 999999 5 8

Sample Output 3



  • 0
    d3story  commented on Feb. 7, 2021, 6:48 p.m. edit 2

    Can someone please take a look at my code I spent a lot of time but I can't seem to find what is wrong?

    Ps I took a look at the editorial I think it has something to do with the big numbers. I think my logic is correct

    • 1
      Kirito  commented on Feb. 7, 2021, 7:26 p.m.

      Hint: compute 2^{30}, and then take it modulo 10^9 + 7.

      Note that this number is not even. What does tell you about naively combining division and modulo operations?

      • 0
        d3story  commented on Feb. 7, 2021, 10:07 p.m. edit 2

        Is there any good way to overcome this though, I tried to use the Modular inverse thing to find a solution But I am quite sure it doesn't work 100% of the time.

        btw tysm for helping