【题目来源】
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/
