DMOPC '14 Contest 5 P6 - Nia and Dominoes

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 4.5s
Memory limit: 32M

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, but some of Nia's dominoes are broken, and they have dimensions 1 \times 1.

Nia wants to make a line of dominoes with dimensions N \times 1. Nia has A types of 1 \times 1 dominoes and B types of 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 line of dominoes using 2 \times 1 and 1 \times 1 dominoes. Two ways are considered different if they do not have the same number of dominoes or the i^{th} domino in one way is of a different length or type than the i^{th} domino in the other way (counting from the beginning, for any i).

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

Input Specification

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

The second line of input will have 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.


For all subtasks:

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

M > 100

Subtask 1 [10%]

1 \le N \le 100\,000

Subtask 2 [30%]

1 \le N \le 10^9

Subtask 3 [60%]

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

Sample Input 1

1 1 101

Sample Output 1


Sample Input 2

0 1 101

Sample Output 2


Sample Input 3

1 0 101

Sample Output 3


Sample Input 4

2 0 10007

Sample Output 4


Sample Input 5

123 456 787

Sample Output 5


Sample Input 6

956 381 10009

Sample Output 6


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


  • 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.


          bobhob314 swaglordof80085

          Edit 2: By the way,

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