斐波那契前 n 项和 - 矩阵乘法快速幂

本文主要是介绍斐波那契前 n 项和 - 矩阵乘法快速幂，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1303. 斐波那契前 n 项和 - AcWing题库

构造矩阵A使

                              0        1        0

 A        =          [      1        1        1        ]

                              0        0        1

然后对这个式子进行快速幂，挺神奇的

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef pair<int, int> PII;
typedef long long ll;
typedef long double ld;const int N = 3;int n, mod;void mul(int C[], int A[], int B[][N])
{int tmp[N] = {0};for(int i = 0; i < N; i ++)for(int j = 0; j < N; j ++)tmp[i] = (tmp[i] + (ll)A[j] * B[j][i]) % mod;memcpy(C, tmp, sizeof tmp);
}void mul(int C[][N], int A[][N], int B[][N])
{int tmp[N][N] = {0};for(int i = 0; i < N; i ++)for(int j = 0; j < N; j ++)for(int k = 0; k < N; k ++)tmp[i][j] = (tmp[i][j] + (ll)A[i][k] * B[k][j]) % mod;memcpy(C, tmp, sizeof tmp);
}int main()
{IOSint f1[N] = {1, 1, 1};int A[N][N] = {{0, 1, 0}, {1, 1, 1}, {0, 0, 1}};cin >> n >> mod;int k = n - 1;while(k){if(k & 1)mul(f1, f1, A);//f1 = f1 * A mul(A, A, A);//A = A * Ak >>= 1;}cout << f1[2];return 0;
} 

这篇关于斐波那契前 n 项和 - 矩阵乘法快速幂的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---