传送门
ITX351 要铺一条 2 × n 2×n 2×n 的路，为此他购买了 n n n 块 2 × 1 2×1 2×1 的方砖。可是其中一块砖在运送的过程中从中间裂开了，变成了两块 1 × 1 1×1 1×1 的砖块！
ITX351 由此产生了一个邪恶的想法：他想要在这条路上故意把两块 1 × 1 1×1 1×1 的砖块分开铺，不让这两块砖有相邻的边，其他砖块可以随意铺，直到整条路铺满。这样一定可以逼死自身强迫症 sea5！
请你帮忙计算一下，有多少种方案可以让自己的阴谋得逞。
有 T T T 组数据。
数据范围： T ≤ 500 T\le500 T≤500， n ≤ 2 × 1 0 9 n\le 2\times 10^9 n≤2×109。
我们设 f i f_i fi 表示 n = i n=i n=i 的答案，考虑递推。即如果在 2 × ( i − 1 ) 2\times (i-1) 2×(i−1) 的基础上加一列，变成 2 × i 2\times i 2×i，那么：
比较容易发现的是，当我们在红色位置放 1 × 1 1\times 1 1×1 的砖时，另一块砖只能放在蓝色位置： 而且下图中的紫色部分只有一种固定的放法，而黄色部分可以用 2 × 1 2\times 1 2×1 的砖随意放： 上面只是举了几个例子，我不会证，但应该足以让我们看出规律了。
我们设 g i g_i gi 表示用 2 × 1 2\times 1 2×1 的砖铺 2 × i 2\times i 2×i 区域的方案， h i h_i hi 为其前缀和，那么这部分答案应该是 2 h i − 3 2h_{i-3} 2hi−3（有个 2 2 2 是因为红砖可以摆在下面，是一模一样的情况）。
发现 g i g_i gi 是斐波那契数列，证法与 “ “ “最后一列不放 1 × 1 1\times 1 1×1 的砖 ” ” ”类似，我就不证了。
又因为斐波那契数列前缀和 h i = g i + 2 − 1 h_i=g_{i+2}-1 hi=gi+2−1，证法就是先给第一项加个 1 1 1，然后逐个合并后再 − 1 -1 −1。
所以，综上，我们终于推出 f i f_i fi 的表达式：
f i = f i − 1 + f i − 2 + 2 g i − 1 − 2 f_i=f_{i-1}+f_{i-2}+2g_{i-1}-2 fi=fi−1+fi−2+2gi−1−2
这可以写成矩阵的形式：
[ 1 1 2 0 − 2 1 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 1 ] [ f i − 1 f i − 2 g i − 1 g i − 2 1 ] = [ f i f i − 1 g i g i − 1 1 ] \begin{bmatrix}1&1&2&0&-2\\1&0&0&0&0\\0&0&1&1&0\\0&0&1&0&0\\0&0&0&0&1\end{bmatrix} \begin{bmatrix}f_{i-1}\\f_{i-2}\\{g_{i-1}}\\g_{i-2}\\1\end{bmatrix}= \begin{bmatrix}f_i\\f_{i-1}\\g_i\\g_{i-1}\\1\end{bmatrix} ⎣⎢⎢⎢⎢⎡11000100002011000100−20001⎦⎥⎥⎥⎥⎤⎣⎢⎢⎢⎢⎡fi−1fi−2gi−1gi−21⎦⎥⎥⎥⎥⎤=⎣⎢⎢⎢⎢⎡fifi−1gigi−11⎦⎥⎥⎥⎥⎤
然后就可以愉快的矩阵快速幂啦。
时间复杂度 O ( 5 3 T log n ) O(5^3T\log n) O(53Tlogn)。
