# Nowcoder 105G 又见斐波那契 （矩阵快速幂）

## 题目描述

$$F(i)= \begin{cases} F(i-1) + F(i-2) + i^3 + i^2 + i + 1 & & i>1 \\ 0 & & i=0 \\ 1 & & i=1 \end{cases}$$

## 输入

4
1
2
3
100


## 输出

1
16
57
558616258


## 思路

$$\begin{bmatrix} F_i \\ F_{i-1} \\ (i+1)^3 \\ (i+1)^2 \\ i+1 \\ 1 \end{bmatrix} \Longleftarrow \begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 3 & 3 & 1 \\ 0 & 0 & 0 & 1 & 2 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ \end{bmatrix} \times \begin{bmatrix} F_{i-1} \\ F_{i-2} \\ i^3 \\ i^2 \\ i \\ 1 \end{bmatrix}$$

## AC 代码

#include <bits/stdc++.h>
#define IO                       \
ios::sync_with_stdio(false); \
cin.tie(0);                  \
cout.tie(0);
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
const LL meix[6][6] = {{
1,
1,
1,
1,
1,
1,
},
{
1,
0,
0,
0,
0,
0,
},
{
0,
0,
1,
3,
3,
1,
},
{
0,
0,
0,
1,
2,
1,
},
{
0,
0,
0,
0,
1,
1,
},
{
0,
0,
0,
0,
0,
1,
}};

class marx {
public:
marx() { memset(mp, 0, sizeof(mp)); }
LL mp[6][6];
static marx mult(const marx &x, const marx &y) {
marx res = marx();
for (LL i = 0; i < 6; i++)
for (LL j = 0; j < 6; j++)
for (LL k = 0; k < 6; k++)
res.mp[i][j] =
(res.mp[i][j] + x.mp[i][k] * y.mp[k][j]) % mod;
return res;
};
} init;

marx mult(const marx &x, LL k) {
marx tmp = marx();
marx tmpx = x;
for (int i = 0; i < 6; i++) {
tmp.mp[i][i] = 1;
}
while (k) {
if (k & 1)
tmp = init.mult(tmp, tmpx);
tmpx = init.mult(tmpx, tmpx);
k >>= 1;
}
return tmp;
}

int main() {
#ifdef LOCAL_IM0QIANQIAN
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#else
IO;
#endif // LOCAL_IM0QIANQIAN
int T;
cin >> T;
marx res = marx();
memcpy(res.mp, meix, sizeof(meix));

while (T--) {
LL n;
cin >> n;
if (n <= 1) {
cout << n << endl;
continue;
}
marx ans = mult(res, n - 1);
cout << (ans.mp[0][0] + ans.mp[0][2] * 8 + ans.mp[0][3] * 4 +
ans.mp[0][4] * 2 + ans.mp[0][5]) %
mod
<< endl;
}
return 0;
}