解題區/解題區 - UVa

UVa 12446 - How Many... in 3D!

contents

  1. 1. Problem
  2. 2. Output Format
  3. 3. Sample Input
  4. 4. Sample Output
  5. 5. Solution

Problem

Given a 2x2xN box, in how many ways can you fill it with 1x1x2 blocks?
Input Format

The input starts with an integer T - the number of test cases (T <= 10,000). T cases follow on each subsequent line, each of them containing the integer N (1 <= N <= 1,000,000).

Output Format

For each test case, print the number of ways to fill the box modulo 1,000,000,007

Sample Input

1
2
3
4
3
1
2
3

Sample Output

1
2
3
2
9
32

Solution

把幾種情況畫出來，會發現有一種特別的之之型，最後會接上一個 1x2 的來湊滿一個 2 x 2 x N 的情況，為此我們必須要知道有多少這種之之型可以從哪裡拆分出來。

會在代碼中發現一個變數 c 存放的便是以之之型結束的方法數，之之型可以把最後一個 1x2 拿走，繼續延伸。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <stdio.h>
#include <algorithm>
using namespace std;
long long dp[1048576] = {};
const long long mod = 1000000007LL;
int main() {
    dp[0] = 1, dp[1] = 2, dp[2] = 9, dp[3] = 32;
    long long c = 4;
    for(int i = 4; i <= 1000000; i++) {
        c = (c + dp[i-3] * 4)%mod; // {ZigZag}
        dp[i] = (dp[i-1] * 2 + dp[i-2] * 5 + c)%mod; 
    }
    int testcase, n;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        printf("%d\n", dp[n]);
    }
    return 0;
}
/*
1000
1
2
3
4
5
6
7
2
9
32
121
450
1681
6272
*/