首先,这题需要开 `long long`。
上面自己写的类我没看,但是我 `main` 是这么写的。
```cpp
#define int long long
...(一个自定义类 Matrix)
int T,n;
/*
1 0 1
1 0 0
0 1 0
*/
Matrix P;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(nullptr),cout.tie(nullptr);
cin >> T;
P.m=P.n=3;
P[1][1]=P[1][3]=P[2][1]=P[3][2]=1;
while(T--)
{
cin >> n;
// P^n 为重载运算符,即 P 的 n 次方
cout << (P^n)[2][1] << endl;
}
return 0;
}
```
by SlaineTroyard @ 2023-01-17 13:59:42
AC代码可以参考一下
```cpp
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
struct Matrix {
long long m[3][3];
int n;
};
Matrix matrix_mul(Matrix a, Matrix b, int mod) {
Matrix sum;
memset(sum.m, 0, sizeof(sum.m));
sum.n = a.n;
for (int i = 0; i < sum.n; i++) {
for (int j = 0; j < sum.n; j++) {
for (int k = 0; k < a.n; k++) {
sum.m[i][j] = (sum.m[i][j] + a.m[i][k] * b.m[k][j] % mod) % mod;
}
}
}
return sum;
}
Matrix matrix_unit(int n) {
Matrix unit;
unit.n = n;
for (int i = 0; i < unit.n; i++) {
for (int j = 0; j < unit.n; j++) {
if (i == j) {
unit.m[i][j] = 1;
} else {
unit.m[i][j] = 0;
}
}
}
return unit;
}
Matrix matrix_pow(Matrix x, long long p, int mod) {
Matrix res = matrix_unit(x.n);
while (p) {
if (p & 1) {
res = matrix_mul(res, x, mod);
}
x = matrix_mul(x, x, mod);
p >>= 1;
}
return res;
}
int t;
long long n;
Matrix tmp;
Matrix ans;
int main() {
cin >> t;
tmp.m[0][1] = 1;
tmp.m[1][2] = 1;
tmp.m[2][0] = 1;
tmp.m[2][2] = 1;
tmp.n = 3;
while (t--) {
memset(ans.m, 0, sizeof(ans.m));
cin >> n;
if (n <= 3) {
cout << 1;
cout << endl;
} else {
ans = matrix_pow(tmp, n - 2, mod);
cout << (ans.m[0][2] + ans.m[2][2]) % mod;
cout << endl;
}
}
}
```
by 崔泽禹 @ 2023-01-17 13:59:42
@[Franz_Liszt](/user/450246) 谢谢
by Ruan_ji @ 2023-01-17 14:00:34
@[Franz_Liszt](/user/450246) 感谢
by Ruan_ji @ 2023-01-17 14:00:50