Please No More Sigma（构造矩阵）

Please No More Sigma

给f(n)定义如下：

f(n)=1 n=1,2;

f(n)=f(n-1)+f(n-2) n>2;

给定n，求下式模1e9+7后的值

Input

第一行一个数字T，表示样例数
以下有T行，每行一个数，表示n。
保证T<=100，n<=100000000

Output

输出式子的值。由于直接求值会很大，输出模1e9+7后的结果。

Sample Input

2
1
2

Sample Output

1
4

思路：

写出前几项的形式；

设g(n)为i=n时的和，s(n)为f(n)前n项和，h（n）为i=1到i=n的总和。

可以找到规律：

g(n)=g(n-1)+s(n)；

h(n)=h(n-1)+g(n);

然后构造矩阵：

代码：

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<unordered_map>
#include<map>
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
#define per(i,a,b) for(int i=a;i<=b;i++)
#define ber(i,a,b) for(int i=a;i>=b;i--)
const int N = 1e5;
const long long mod = 1e9 + 7;
const double eps = 1e-2;
typedef struct data
{
LL m[5][5];

}J;
J Q, E;
J now, ans;
LL f[5];
void into()
{
Q = { 0,1,0,0,0,
1,1,0,0,0,
0,1,1,0,0,
0,0,1,1,0,
0,0,0,1,1,};
E = { 1,0,0,0,0,
0,1,0,0,0,
0,0,1,0,0,
0,0,0,1,0,
0,0,0,0,1};
}
J quickfu(J a, J b)
{
J c;
for (int i = 0; i <= 4; i++)
for (int j = 0; j <= 4; j++)
{
c.m[i][j] = 0;
for (int k = 0; k <= 4; k++)
c.m[i][j] = (c.m[i][j] + a.m[i][k] * b.m[k][j] % mod) % mod;
c.m[i][j] = (c.m[i][j] % mod + mod) % mod;
}
return c;
}
J quick(J a, LL b)
{
J ans = E;
while (b)
{
if (b & 1)
ans = quickfu(ans, a);
b >>= 1;
a = quickfu(a, a);
}
return ans;
}
LL n;
int main()
{
int T;
cin >> T;
into();
while (T--)
{
cin >> n;
if (n == 0)
{
cout << 0 << endl;
continue;
}
else if (n == 1)
{
cout << 1 << endl;
continue;
}
f[0] = 1, f[1] =2 , f[2] = 2, f[3] = 1,f[4]=0;
now = Q;
ans = quick(now, n);
LL an = 0;
for (int i = 0; i <= 4; i++)
an = (an + ans.m[4][i] * f[i] % mod) % mod;
cout << (an % mod + mod) % mod << endl;
}