矩阵快速幂，递推
难度是递推关系，加入红色 用1表示， 蓝色用0 表示，一串就是一个 01 字符串。任意素数长度范围内，1 的个数 >= 0 的个数。
假如有一条合法的 01 串，位数是n， 合法项链数是 f(n). 在这条 01 串后面加1， 必然满足要求。
构成的长度 n + 1 的新串，以 1 结尾的合法串项链数 f(n)。
如果在这条n长度的 01 串后面加0， 相当于 长度为 n - 2 的 01 串后面加上 3位， 其中 第 n + 1 位确定是0， 剩下的第 n - 1 和 n 位， 有4种可能：
00， 01， 10， 11， 补上第 n + 1 位的0就是 000， 010， 100， 110. 显然只有 110 符合要求。
构成的长度 n + 1 的新串，以 0 结尾的合法串个数是 f(n - 2)
综上 f(n + 1) = f(n) + f(n - 2);
递推公式 n >= 4, f(n) = f(n- 1) + f(n - 3)
本题要点：
1、起始矩阵 res.m 如下
res.m[0][0] = f(4), res.m[0][1] = f(3), res.m[0][2] = f(2)
res.m[1][0] = 0, res.m[1][1] = 0, res.m[1][2] = 0
res.m[2][0] = 0, res.m[2][1] = 0, res.m[2][2] = 0
2、乘上矩阵 a.m 的 n - 4 的幂次， 矩阵 a.m 如下
a.m[0][0] = 1, a.m[0][1] = 1, a.m[0][2] = 0
a.m[1][0] = 0, a.m[1][1] = 0, a.m[1][2] = 1
a.m[2][0] = 1, a.m[2][1] = 0, a.m[2][2] = 0
3、注意 Matrix 的矩阵m一定要用 long long， 否则会爆 int
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MaxN = 3;
int ans[5];
int T;
long long n, mod = 1e9 + 7;;struct Matrix
{
long long m[MaxN][MaxN];Matrix(){
memset(m, 0, sizeof m);}
};Matrix multi(Matrix a, Matrix b)
{
Matrix res;for(int i = 0; i < MaxN; ++i)for(int j = 0; j < MaxN; ++j){
for(int k = 0; k < MaxN; ++k){
res.m[i][j] = (res.m[i][j] + a.m[i][k] * b.m[k][j]) % mod;} //m一定要用 long long， 否则会爆 int}return res;
}Matrix fastm(Matrix res, Matrix a, long long n)
{
while(n){
if(n & 1){
res = multi(res, a);}a = multi(a, a);n >>= 1;}return res;
}void solve()
{
if(n <= 4){
printf("%d\n", ans[n]);return;}Matrix res, a;res.m[0][0] = ans[4], res.m[0][1] = ans[3], res.m[0][2] = ans[2];a.m[0][0] = a.m[0][1] = a.m[1][2] = a.m[2][0] = 1;res = fastm(res, a, n - 4);printf("%lld\n", res.m[0][0]);
}int main()
{
ans[4] = 6, ans[2] = 3, ans[3] = 4;scanf("%d", &T);while(T--){
scanf("%lld", &n);solve(); }return 0;
}/* 2 2 3 *//* 3 4 */