#include<bits/stdc++.h> using namespace std; using ll = long long; const ll N = 3; ll T; ll n; long long p = 998244353; struct Node { long long m[N][N]; Node() { memset(m, 0, sizeof m); }//矩阵初始化为0的操作 Node operator*(const Node &b) const//定义矩阵乘法运算 { Node c; for (ll i = 0; i < N; i++) for (ll j = 0; j < N; j++) for (ll k = 0; k < N; k++) { c.m[i][j] = (c.m[i][j] + m[i][k] * b.m[k][j]) % p; } return c; } }; Node fun(Node a, long long b) { Node res; for (ll i = 0; i < N; i++) res.m[i][i] = 1;//构造单位矩阵res while (b) { if (b & 1) res = res * a; // 对于奇数次幂,把矩阵a乘到res上 a = a * a; b = b / 2; } return res; } Node x,y; long long fun1() { x.m[0][0] = 1; x.m[0][1] = 0; x.m[0][2] = 1; x.m[1][0] = 0; x.m[1][1] = 1; x.m[1][2] = 1; x.m[2][0] = 2; x.m[2][1] = 2; x.m[2][2] = 1; y = fun(x,n-1); cout << (y.m[0][0] + y.m[0][2] * 2)%p <<"\n"; return y.m[0][0]; } int main() { cin >> T; for(int i = 0; i< T; i++) { cin >> n; fun1(); } return 0; }分析思路
时间: 2024-04-27 14:19:22 浏览: 144
万能头文件#include“bitsstdc++.h”.pdf
这段代码是使用矩阵快速幂来求解斐波那契数列的第 n 项,时间复杂度为 O(log n)。
具体分析如下:
1. 定义一个 3x3 的矩阵 Node,其中 Node.m[i][j] 表示第 i 行第 j 列的元素。
2. 定义一个 fun 函数,其中参数 a 为一个 Node 矩阵,b 为一个整数。函数返回一个 Node 矩阵,表示 a 的 b 次幂。
3. 在 fun 函数中,首先构造一个单位矩阵 res,然后进行循环操作,每次将 a 的平方赋值给 a,b 右移一位。如果当前 b 的最低位为 1,就将 res 乘上 a,然后将 a 赋值为 a 的平方。最后返回 res。
4. 定义一个 fun1 函数,其中初始化一个 1x3 的矩阵 x,然后根据斐波那契数列的递推公式构造一个 3x3 的矩阵 y,将 y 赋值为 x 的 n-1 次幂,然后输出 y.m[0][0] + y.m[0][2] * 2 的值,即斐波那契数列的第 n 项。注意取模操作。
5. 在 main 函数中,读入测试数据的数量 T,然后进行 T 次循环,每次调用 fun1 函数。
因为矩阵快速幂的时间复杂度为 O(log n),所以整个程序的时间复杂度为 O(T * log n)。
阅读全文