DMOPC '14 Contest 5 P6 - Nia and Dominoes - Olympiads Online Judge

DMOPC '14 Contest 5 P6 - Nia and Dominoes

Points: 20 (partial)

Time limit: 4.5s

Memory limit: 32M

Author:

Problem type

While she was living in the Spiral King's castle, Nia had lots of free time. One day, she decided to pass the time by building a very, very long line of dominoes.

A typical domino has dimensions $2 \times 1$ ~2 \times 1~, but some of Nia's dominoes are broken, and they have dimensions $1 \times 1$ ~1 \times 1~.

Nia wants to make a line of dominoes with dimensions $N \times 1$ ~N \times 1~. Nia has $A$ ~A~ types of $1 \times 1$ ~1 \times 1~ dominoes and $B$ ~B~ types of $2 \times 1$ ~2 \times 1~ dominoes. For each type of domino, Nia has an unlimited amount at her disposal. Dominoes need to have a fixed orientation in order to connect together in the line, so they cannot be rotated. Now Nia wonders how many possible ways she can make an $N \times 1$ ~N \times 1~ line of dominoes using $2 \times 1$ ~2 \times 1~ and $1 \times 1$ ~1 \times 1~ dominoes. Two ways are considered different if they do not have the same number of dominoes or the $i^{th}$ ~i^{th}~ domino in one way is of a different length or type than the $i^{th}$ ~i^{th}~ domino in the other way (counting from the beginning, for any $i$ ~i~).

Since this number may be large, please compute it modulo $M$ ~M~.

Input Specification

The first line of input will have $A$ ~A~, $B$ ~B~, and $M$ ~M~.

The second line of input will have $N$ ~N~.

Warning: The input is extremely large (up to 100MB). Please be careful with input methods (i.e. use the fastest possible input method your language supports). Take special note that the memory limit for this problem is 32MB. It is not guaranteed that a language slower than C/C++ can score full marks.

Output Specification

Output the answer on a single line.

Constraints

For all subtasks:

$0 \le A, B < M \le 10\,009$ ~0 \le A, B < M \le 10\,009~

$M > 100$ ~M > 100~

Subtask 1 [10%]

$1 \le N \le 100\,000$ ~1 \le N \le 100\,000~

Subtask 2 [30%]

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

Subtask 3 [60%]

$1 \le N \le 10^{(10^8)}$ ~1 \le N \le 10^{(10^8)}~

Sample Input 1

1 1 101
9

Sample Output 1

Sample Input 2

0 1 101
1337

Sample Output 2

Sample Input 3

1 0 101
2015

Sample Output 3

Sample Input 4

2 0 10007
1234567890

Sample Output 4

Sample Input 5

123 456 787
88888888

Sample Output 5

Sample Input 6

956 381 10009
705923593712956959302756329278756282035756528101747656392654937104729

Sample Output 6

In the spirit of Tengen Toppa Gurren Lagann, we have ramped up the test data to 11 for this problem.

Comments

2

bossu commented on April 1, 2015, 1:45 p.m.

is there any way to get AC on this problem? reading 100 MB seems too much...

-1

FatalEagle commented on April 1, 2015, 2:28 p.m. ← edit 2 →

Reading 100MB is fine if you use getchar(). The time limit is 4.5s.

2

bossu commented on April 1, 2015, 3:51 p.m. ← edited →

thanks, got ac using getchar()

-4

bobhob314 commented on April 14, 2015, 10:49 p.m. ← edit 10 →

Hi bossu, may I please inquire

Who in the friggity floppity cow dongus are you? Were you once a Thornhill Master Race L33t Programm3r? If so, please teach me. Otherwise, please teach me. Edit: I ask because your organization is listed as Thornhill S.S.

Thanks,

bobhob314 swaglordof80085

Edit 2: By the way,

Write the Special Day Contest on [2015-0] 4-20 at 3:30 PM!