FDU 2018 | 3. 骨牌

1. 题目描述

用 1 × 2 1×2 1×2 和 2 × 1 2×1 2×1 的骨牌铺满大小为 2 × n 2×n 2×n 的地板，请问共有多少种不同铺法。

输入格式
一个整数 n n n 。

输出格式
一个整数，表示铺法数量对 999983 999983 999983 取模后的结果。

数据范围
1 ≤ n ≤ 10000 1≤n≤10000 1≤n≤10000

输入样例

6

输出样例

13

2. 我的尝试

#include <bits/stdc++.h>
using namespace std;

const int N = 10010, MOD = 999983;
int f[N];

int main()
{
    int n;
    cin >> n;
    
    f[1] = 1, f[2] = 2;
    for (int i = 3; i <= n; i++)
    {
        f[i] = (f[i - 1] + f[i - 2]) % MOD;
    }
    
    cout << f[n];
    return 0;
}