本关任务:设计一个2*2的矩阵结构体,然后计算一个矩阵 A 的 n 次幂。为了避免整型溢出,请输出矩阵中每个元素模 10^9+7 后的结果 编程要求 根据提示,在右侧编辑器补充代码,用户先输入一个整数 n 代表幂次,然后四个整型数a, b, c ,d ,分别代表矩阵 A 的四个元素。 A=( a c b d ) 输出A^n中每个元素模10^9+7后的结果。注意:0≤n≤10 9 ,直接使用循环乘法可能会超时,请观察如下整数的快速幂算法,仿写矩阵的快速幂算法。算法复杂度 O(logn) int fpower(int x, int n) { // 计算 x^n, 复杂度 O(log n) int ans = 1; while (n) { if (n % 2) ans *= x; x *= x; n /= 2; } return ans; }
时间: 2024-03-26 13:34:36 浏览: 191
```
#include <iostream>
using namespace std;
const int mod = 1e9 + 7;
struct Matrix {
int m[2][2];
Matrix() {
memset(m, 0, sizeof(m));
}
Matrix operator*(const Matrix& other) const {
Matrix res;
for(int i = 0; i < 2; i++)
for(int j = 0; j < 2; j++)
for(int k = 0; k < 2; k++)
res.m[i][j] = (res.m[i][j] + 1ll * m[i][k] * other.m[k][j]) % mod;
return res;
}
};
Matrix qmi(Matrix a, int b) {
Matrix res;
res.m[0][0] = res.m[1][1] = 1;
while(b) {
if(b & 1) res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
int main() {
int n, a, b, c, d;
cin >> n >> a >> b >> c >> d;
Matrix A;
A.m[0][0] = a, A.m[0][1] = b;
A.m[1][0] = c, A.m[1][1] = d;
Matrix res = qmi(A, n);
cout << res.m[0][0] % mod << " " << res.m[0][1] % mod << endl;
cout << res.m[1][0] % mod << " " << res.m[1][1] % mod << endl;
return 0;
}
```
阅读全文