XidianOJ 1109 Too Naive

题目描述

在一个2 x n的矩形中，用一些2 x 1 和 一些3 x 2的小矩形去覆盖它（小矩形可旋转），不能有重叠也不能有遗漏，小矩形也不能超出边界，求覆盖的方案数（不考虑旋转和翻转），并对10007取模。

输入

多组测试数据（大约10000组），处理到EOF。
每组数据包含一行，表示n（1 ≤ n ≤ 106）。

输出

对于每组数据输出一行，表示方案数对10007取模。

--正文

递推即可

f[n] = f[n-1] + f[n-2] + f[n-3] 

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define MOD 10007
#define SIZE 1000000
int f[SIZE+1];

int main(){
    int i,j;
    f[0] = 1; f[1] = 1; f[2] = 2; 
    for (i=3;i<=SIZE;i++){
        f[i] = (f[i-3]+f[i-2]+f[i-1]) % MOD;
    }
    int n;
    while (scanf("%d",&n) != EOF){
        printf("%d
",f[n]);
    } 
    return 0;
}