$$【组合数学】专题笔记目录$$

考虑只有 $1 \times 2$ 方块的时候，构建一个 $2 \times n$ 的区域方案数显然为斐波那契数列。
为什么呢？可以从 $n-2$ 转移而来，就是横着放两个 $1 \times 2$；或者从 $n-1$ 转移而来，竖着放一个 $1 \times 2$。

再来看这一题，放了两个 $1 \times 1$ 的方块之后整个 $2 \times n$ 的区域可以分成三部分：

• 第一个 $1 \times 1$ 方块左边。
• 两个方块之间。
• 第二个 $1 \times 1$ 方块右边。

笔者手残不会画图。

那么答案即为 $2 \times \sum\limits_{x=0}^{n-3} ~ \sum\limits_{y=0}^{(n-3)-x} Fib_x \times Fib_y$。
要 $\times 2$ 是因为两个 $1 \times 1$ 方块之间可以上下行交换。

接下来就是推式子：

$2 \times \sum\limits_{x=0}^{n-3} Fib_x \times \sum\limits_{y=0}^{(n-3)-x} \times Fib_y$

根据 斐波那契数列前缀和定理，可以把后面的前缀和化简：

$2 \times \sum\limits_{x=0}^{n-3} Fib_x \times (Fib_{n-1-x} - 1)$
$2 \times (\sum\limits_{x=0}^{n-3} Fib_x \times Fib_{n-1-x} - Fib_x)$
$2 \times \sum\limits_{x=0}^{n-3} (Fib_x \times Fib_{n-1-x}) - 2 \times (Fib_{n-1} - 1)$

由于后面的 $2 \times (Fib_{n-1} - 1)$ 可以直接求出，所以现在只考虑如何求出 $\sum\limits_{x=0}^{n-3} (Fib_x \times Fib_{n-1-x})$。

把它写成一般形式：$g_x=\sum\limits_{x=0}^{n} (Fib_x \times Fib_{n-x})$
由于 $Fib_0 = Fib_1 = 1$，所以把第 $n-1$ 项和第 $n$ 项都提出来得到：$\sum\limits_{x=0}^{n-2} (Fib_x \times Fib_{n-x}) + Fib_{n-1} + Fib_{n}$
拆 $Fib_{n-x}$ 得：$\sum\limits_{x=0}^{n-2} (Fib_x \times Fib_{n-x-1}) + \sum\limits_{x=0}^{n-2} (Fib_x + Fib_{n-x-2}) + Fib_{n-1} + Fib_{n}$
观察到第二项求和已经是一个 $g_{n-2}$ 的形式了，所以考虑把 $Fib_{n-1}$ 扔到第一个求和里面得：$\sum\limits_{x=0}^{n-1} (Fib_x \times Fib_{n-x-1}) + \sum\limits_{x=0}^{n-2} (Fib_x + Fib_{n-x-2}) + Fib_{n}$

即 $$g_n = g_{n-1} + g_{n-2} + Fib_n$$

由于 $n$ 的毒瘤数据范围，考虑用矩阵快速幂优化递推过程。

这题的推式子真的逼死了我这个强迫症。

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
struct Mat {
    int a[5][5];
    void init() {
        for (int i = 0; i < 5; i++)
            for (int j = 0; j < 5; j++) a[i][j] = 0;
    }
} a, b;

Mat mul(Mat a, Mat b) {
    Mat c; c.init();
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++)
            for (int k = 0; k < 5; k++)
                c.a[i][j] = (c.a[i][j] + ((long long)a.a[i][k] * (long long)b.a[k][j]) % mod) % mod;
    return c;
}

Mat qmi(Mat a, int k) {
    Mat res; res.init();
    for (int i = 0; i < 5; i++) res.a[i][i] = 1;
    while (k) {
        if (k & 1) res = mul(res, a);
        a = mul(a, a);
        k >>= 1;
    }
    return res;
}

int T, n;

int main() {
    scanf("%d", &T);
    b = (Mat) {{
        {1, 1, 0, 0, 0}, 
        {1, 0, 0, 0, 0}, 
        {2, 0, 1, 1, 0}, 
        {0, 0, 1, 0, 0}, 
        {1, 0, 0, 0, 1}
    }};
    while (T--) {
        scanf("%d", &n);
        if (n < 3) {
            puts("0");
            continue;
        }
        a.init();
        a.a[0][2] = 2, a.a[0][3] = 1, a.a[0][4] = mod - 2;
        int ans = mul(a, qmi(b, n - 2)).a[0][0];
        printf("%d\n", (ans % mod + mod) % mod);
    }
    return 0;
}