DMOPC '20 Contest 3 P3 - A Ring of Buckets - Olympiads Online Judge

DMOPC '20 Contest 3 P3 - A Ring of Buckets

Points: 12 (partial)

Time limit: 2.0s

Memory limit: 256M

Author:

Problem types

Lily has a ring of $N$ ~N~ buckets, numbered from $1$ ~1~ to $N$ ~N~. Each bucket has capacity $M$ ~M~. She has a pouring bucket with capacity $K+2$ ~K+2~, and wants to fill all buckets completely without any overflow, that is, to $M$ ~M~ exactly. Unfortunately, every time she tries to pour into a bucket, she spills a little, and $1$ ~1~ unit is spilled into each adjacent bucket, with $K$ ~K~ poured into her original bucket. Note that $1$ ~1~ and $N$ ~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$ ~N~ numbers, so she decides on the following formula. If $A_i$ ~A_i~ is the number of times you must pour into the $i$ ~i~th bucket, Lily will choose an arbitrary number $B$ ~B~ and ask you to compute $A_1 + A_2 \times B + A_3 \times B^2 + \dots + 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$ ~10^9 + 7~. Additionally, if there are multiple solutions, choose the one that has the lexicographically smallest value of $A_1, A_2, \dots, A_N$ ~A_1, A_2, \dots, A_N~.

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

Constraints

For all subtasks:

$1 \le M,K \le 10^9$ ~1 \le M,K \le 10^9~

$2 \le B \le 10^9$ ~2 \le B \le 10^9~

$3 \le N \le 10^9$ ~3 \le N \le 10^9~

$1 \le Q \le 10^4$ ~1 \le Q \le 10^4~

Subtask 1 [1/15]

$Q = 1$ ~Q = 1~

$N,M,K \le 5$ ~N,M,K \le 5~

Subtask 2 [2/15]

$Q = 1$ ~Q = 1~

$N,M,K \le 400$ ~N,M,K \le 400~

Subtask 3 [3/15]

$Q = 1$ ~Q = 1~

$K = 1$ ~K = 1~

$1 \le N,M \le 10^6$ ~1 \le N,M \le 10^6~

Subtask 4 [3/15]

$Q = 1$ ~Q = 1~

$K = 2$ ~K = 2~

$1 \le N,M \le 10^6$ ~1 \le N,M \le 10^6~

Subtask 5 [3/15]

$Q = 1$ ~Q = 1~

$3 \le K \le 10^6$ ~3 \le K \le 10^6~

$1 \le N,M \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$ ~Q~, the number of questions.

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

Output Specification

Output $Q$ ~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$ ~10^9 + 7~.

Sample Input 1

1
4 4 1 100

Sample Output 1

-1

Explanation for Sample Output 1

There is no way to fill all the buckets exactly.

Sample Input 2

1
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

1
999999 999999 5 8

Sample Output 3

35952588

Comments

0

d3story commented on Feb. 7, 2021, 11: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? https://dmoj.ca/src/3377250

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. 8, 2021, 12:26 a.m.

Hint: compute $2^{30}$ ~2^{30}~, and then take it modulo $10^9 + 7$ ~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. 8, 2021, 3:07 a.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