AcWing 1303：斐波那契前 n 项和 ← 矩阵快速幂加速递推

【题目来源】
https://www.acwing.com/problem/content/1305/
http://poj.org/problem?id=3070

【题目描述】
大家都知道 数列吧，。现在问题很简单，输入 和 ，求 的前 项和 。

【输入格式】
共一行，包含两个整数 和 。

【输出格式】
输出前 项和 的值。

【数据范围】


【输入样例】
5 1000

【输出样例】
12

【算法分析】
★ 矩阵快速幂加速递推
（1）已知  数列递推式为 ，但当 极大时，会超时。
故基于“矩阵快速幂加速递推”的思路，改写数列递推式  为 
改写后的递推式对应的 LaTex 代码为：

[F_n \quad F_{n-1}]=[F_{n-1} \quad F_{n-2}] 
\begin{bmatrix}
1 & 1\\ 
1 & 0
\end{bmatrix}
=[F_{n-2} \quad F_{n-3}] 
\begin{bmatrix}
1 & 1\\ 
1 & 0
\end{bmatrix} 
\begin{bmatrix}
1 & 1\\ 
1 & 0
\end{bmatrix}
=\cdots =[F_1,F_0]
\begin{bmatrix}
1 & 1\\ 
1 & 0
\end{bmatrix}^{n-1}

（2）若令 ，则有 。
据此公式可知，首先求出 ，然后用  左乘，便可得到 ，而  的第一个元素即为 。注意：标红的公式，技巧在于使用了 LaTex 命令： \textcolor{red} {公式}

\textcolor{red} {X_n=X_1\times A^{n-1}}

★ 矩阵快速幂模板：https://blog.csdn.net/hnjzsyjyj/ar左乘ticle/details/143227091


【算法代码】

#include<bits/stdc++.h>
using namespace std;typedef long long LL;
LL A[2][2]= {{1,1},{1,0}
};
LL ans[2]= {1,0}; //save answerint n,m;//Column matrix A * matrix B
void mul1(LL A[], LL B[][2]) {LL t[2]= {0};for(int i=0; i<2; i++)for(int j=0; j<2; j++)t[i]+=A[j]*B[i][j]%m;for(int i=0; i<2; i++)A[i]=t[i]%m;
}//matrix A * matrix B
void mul2(LL A[][2], LL B[][2]) {LL t[2][2]= {0};for(int i=0; i<2; i++)for(int j=0; j<2; j++)for(int k=0; k<2; k++)t[i][j]+=A[i][k]*B[k][j]%m;for(int i=0; i<2; i++)for(int j=0; j<2; j++)A[i][j]=t[i][j]%m;
}int main() {scanf("%d%d",&n,&m);n+=2; //get f[n+2]while(n) { //fastPowif(n & 1) mul1(ans,A);mul2(A,A);n>>=1;}printf("%lld\n", ans[1]-1); //ans[1] is f[n+2]return 0;
}/*
in:
5 1000out:
12
*/

【参考文献】
https://www.acwing.com/blog/content/25/
https://blog.csdn.net/hnjzsyjyj/article/details/143227091
https://www.cnblogs.com/yijiull/p/6641422.html
https://www.acwing.com/solution/content/15121/