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}$ $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 \leq M, K \leq 10^{9}$

$2 \le B \le 10^9$ $2 \leq B \leq 10^{9}$

$3 \le N \le 10^9$ $3 \leq N \leq 10^{9}$

$1 \le Q \le 10^4$ $1 \leq Q \leq 10^{4}$

Subtask 1 [1/15]

$Q = 1$ $Q = 1$

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

Subtask 2 [2/15]

$Q = 1$ $Q = 1$

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

Subtask 3 [3/15]

$Q = 1$ $Q = 1$

$K = 1$ $K = 1$

$1 \le N,M \le 10^6$ $1 \leq N, M \leq 10^{6}$

Subtask 4 [3/15]

$Q = 1$ $Q = 1$

$K = 2$ $K = 2$

$1 \le N,M \le 10^6$ $1 \leq N, M \leq 10^{6}$

Subtask 5 [3/15]

$Q = 1$ $Q = 1$

$3 \le K \le 10^6$ $3 \leq K \leq 10^{6}$

$1 \le N,M \le 10^6$ $1 \leq N, M \leq 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

Copy

1
4 4 1 100

Sample Output 1

Copy

-1

Explanation for Sample Output 1

There is no way to fill all the buckets exactly.

Sample Input 2

Copy

1
3 4 2 7

Sample Output 2

Copy

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$ $1 + 1 \times 7 + 1 \times 7^{2} = 57$

Sample Input 3

Copy

1
999999 999999 5 8

Sample Output 3

Copy

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