本文主要是介绍蓝桥集训之斐波那契前n项和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
蓝桥集训之斐波那契前n项和
-
核心思想：矩阵乘法
-
-
左边求和 右边求和 得到Sn = fn+2 – 1
-
因此只要求出fn+2 即可
-
-
#include <iostream>#include <cstring>#include <algorithm>using namespace std;typedef long long LL;int n,m;int A[2][2] = { //构造的矩阵{1,1},{1,0}};int res[2] = {1,0}; //答案矩阵void mul1(int res[],int A[][2]){int ans[2] = {0};for(int i=0;i<2;i++)for(int j=0;j<2;j++)ans[i] = (ans[i] + (LL)res[j] * A[j][i]) %m;memcpy(res,ans,sizeof ans);}void mul2(int A[][2],int B[][2]){int ans[2][2] = {0};for(int i=0;i<2;i++)for(int j=0;j<2;j++)for(int k=0;k<2;k++)ans[i][j] = (ans[i][j] + (LL)A[i][k] * B[k][j])%m;memcpy(A,ans,sizeof ans);}void qmi(int n){while (n){if (n & 1) mul1(res, A);mul2(A, A);n >>= 1;}}int main(){cin>>n>>m;n+=2;if(m==1){cout<<0<<endl;return 0;}qmi(n);cout<<res[1]-1<<endl;return 0;}
这篇关于蓝桥集训之斐波那契前n项和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
