ALGOSPOT-TILING2（动态规划-斐波那契数列）

问题问题

编写一个程序，计算2xn正方形被2x1正方形填充的次数。

例如，如果n = 5，则有八种方法，如下图所示。

随着n的增加，案例数可能会非常大，因此请打印值除以1000000007。

输入值

输入的第一行给出了测试用例的数量（C <= 50）。此后，n（1 <= n <= 100）被指定为每条C行中的一个自然数。

输出量

对于每个测试用例，在一行上输出剩余的用例数除以1000000007。

输入示例

3
1
5
100

输出示例

1
8
782204094

注意事项

当n=1时，只有一种情况，当n=2的时候，存在两种排列方式，当n=3的时候，发现取决于第一块的摆放：如果第一块竖放，则相当于解决如何摆放剩余两块的情况，如果第一个横放，那么变成最后一块如何摆放，于是得出结论：$x_n=x_{n-1}+x_{n-2}$。其实就是斐波那契数列。

这道题的扩展就是《算法问题实战策略》的P180 非对称铺设 ASYMTILING。

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <cstdio>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>

using namespace std;

vector<int> d = {0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,
 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 
 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 
 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 
 701408733, 134903163, 836311896, 971215059, 807526948, 778742000,
  586268941, 365010934, 951279875, 316290802, 267570670, 583861472, 
  851432142, 435293607, 286725742, 722019349, 8745084, 730764433, 
  739509517, 470273943, 209783453, 680057396, 889840849, 569898238, 
  459739080, 29637311, 489376391, 519013702, 8390086, 527403788, 
  535793874, 63197655, 598991529, 662189184, 261180706, 923369890, 
  184550589, 107920472, 292471061, 400391533, 692862594, 93254120, 
  786116714, 879370834, 665487541, 544858368, 210345902, 755204270, 
  965550172, 720754435, 686304600, 407059028, 93363621, 500422649, 
  593786270, 94208912, 687995182, 782204094};

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int caseNum; cin >> caseNum;
    while (caseNum--) {
        int n; cin >> n;
        cout << d[n] << endl;
    }

    return 0;
}

因为数据范围是1-100，所以可以直接打表。