ITX351 要铺一条 (2 imes n) 的路，为此他购买了 (n) 块 (2 imes 1) 的方砖。可是其中一块砖在运送的过程中从中间裂开了，变成了两块 (1 imes 1) 的砖块！
ITX351 由此产生了一个邪恶的想法：他想要在这条路上故意把两块 (1 imes 1) 的砖块分开铺，不让两块砖有相邻的边，其他砖块可以随意铺，直到整条路铺满。这样一定可以逼死自身强迫症 sea5！
也许下面的剧情你已经猜到了 —— 他为此兴奋不已，以至于无法敲键盘。于是，他请你帮忙计算一下，有多少种方案可以让自己的阴谋得逞。
多组询问。
数据范围：(1 leq T leq 500)，(1 leq n leq 10^9)。
考虑 dp。
令 (f_n) 表示：根据题意，铺设一条 (2 imes n) 的合法道路的方案数。
转移有两种：
-
第 (n) 列不存在 (1 imes 1) 的方砖。
- 在第 (n) 列竖着放一个 (2 imes 1) 的方砖，得到一个规模为 (n - 1) 的子问题。
- 在第 (n - 1) 列和第 (n) 列横着放两个 (2 imes 1) 的方砖，得到一个规模为 (n - 2) 的子问题。
-
第 (n) 列存在 (1 imes 1) 的方砖。
此时，可以考虑另一块 (1 imes 1) 的方砖的位置。
这一块 (1 imes 1) 的方砖只能放在第 (1) 列至第 (n - 2) 列中。
注意到每一列，有且仅有一个位置可填，至于是 " 同行还是异行 " 与 " 列数差的奇偶性 " 有关。更进一步，假设说这个 (1 imes 1) 的方砖放在了第 (i) 列，则：
- ((1)) 第 (i) 列至第 (n) 列里所有方砖的方法是唯一确定的。
- ((2)) 第 (1) 列至第 (i - 1) 列里所有方砖可以随便摆放。
那主要考虑 ((2)) 的情况。
令 (g_n) 表示：只使用 (2 imes 1) 的方砖，铺设一条 (2 imes n) 的合法道路的方案数。显然有：
综上，有转移：
至此，此题已经可以使用矩阵快速幂解决。
但是这个转移看起来就很不爽。
我们希望可以把他化简一下。
注意到数列 ({ g_n }) 与斐波那契数列 ({ fib_n }) 恰好错位了一位。
而斐波那契数列的前缀和有一个非常美妙的性质：
可以使用数学归纳法简单证明一下：
当 (n = 1) 时，命题显然成立。
假设当 (n = m) 时，命题成立。
当 (n = m + 1) 时：[egin{aligned}fib_{m + 3} - 1 & = fib_{m + 1} + fib_{m + 2} - 1\& = fib_{m + 1} + sumlimits_{i = 1} ^ m fib_{i}\& = sumlimits_{i = 1}^{m + 1} fib_iend{aligned} ]故原命题成立，QED。
于是就可以使用斐波那契数代替 (sumlimits_{0 leq i leq n - 3} g_i)，得到转移：
具体的，令设矩阵 (F(n) = egin{bmatrix} f_n & f_{n - 1} & fib_{n} & fib_{n - 1} & -2 end{bmatrix})。
则：
先把 (n = 1, 2) 的情况判掉。
对于 (n geq 3) 的情况，最终的答案矩阵即为 (F(2) ast A^{n - 2})，其中 (A) 为上式中的转移矩阵。
单组数据时间复杂度 (mathcal{O}(5^3 log n))。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int mod = 1e9 + 7;
int n;
int f[6];
int A[6][6];
void mulstar(int f[6], int a[6], int b[6][6]) {
static int c[6]; memset(c, 0, sizeof(c));
for (int j = 1; j <= 5; j ++)
for (int k = 1; k <= 5; k ++)
c[j] = (c[j] + 1ll * a[k] * b[k][j]) % mod;
memcpy(f, c, sizeof(c));
}
void mul(int f[6][6], int a[6][6], int b[6][6]) {
static int c[6][6]; memset(c, 0, sizeof(c));
for (int i = 1; i <= 5; i ++)
for (int j = 1; j <= 5; j ++)
for (int k = 1; k <= 5; k ++)
c[i][j] = (c[i][j] + 1ll * a[i][k] * b[k][j]) % mod;
memcpy(f, c, sizeof(c));
}
void work() {
scanf("%d", &n);
if (n == 1 || n == 2) {
puts("0");
return;
}
// 初始矩阵 F(2)
f[1] = 0, f[2] = 0, f[3] = 1, f[4] = 1, f[5] = mod - 2;
// 转移矩阵 A
A[1][1] = 1, A[1][2] = 1, A[1][3] = 0, A[1][4] = 0, A[1][5] = 0;
A[2][1] = 1, A[2][2] = 0, A[2][3] = 0, A[2][4] = 0, A[2][5] = 0;
A[3][1] = 2, A[3][2] = 0, A[3][3] = 1, A[3][4] = 1, A[3][5] = 0;
A[4][1] = 2, A[4][2] = 0, A[4][3] = 1, A[4][4] = 0, A[4][5] = 0;
A[5][1] = 1, A[5][2] = 0, A[5][3] = 0, A[5][4] = 0, A[5][5] = 1;
for (int b = n - 2; b; b >>= 1) {
if (b & 1) mulstar(f, f, A);
mul(A, A, A);
}
printf("%d
", f[1]);
}
int main() {
int T;
scanf("%d", &T);
while (T --) work();
return 0;
}