当前位置：首页 > news >正文

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

news 2024/10/31 5:45:49

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

【题目描述】
大家都知道 $Fibonacci$ 数列吧， $F_1=1,F_2=1,F_3=2,F_4=3,\cdots ,F_n=F_{n-1}+F_{n-2}$ 。现在问题很简单，输入 $n$ 和 $m$ ，求 $F_n$ 的前 $n$ 项和 $S_n \, mod \, m$ 。

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

【输出格式】
输出前 $n$ 项和 $S_n \, mod \, m$ 的值。

【数据范围】
$1\leq n \leq 2000000000,\\ 1 \leq m \leq1000000010$

【输入样例】
5 1000

【输出样例】
12

【算法分析】
★ 矩阵快速幂加速递推
（1）已知 $Fibonacci$ 数列递推式为 $F_n=F_{n-1}+F_{n-2}$ ，但当 $n$ 极大时，会超时。
故基于“矩阵快速幂加速递推”的思路，改写数列递推式 $F_n=F_{n-1}+F_{n-2}$ 为 $[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}$
改写后的递推式对应的 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）若令 $X_n=[F_n \quad F_{n-1}], \, X_1=[F_1 \quad F_0], \, A=\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}$ ，则有 $\textcolor{red} {X_n=X_1\times A^{n-1} }$ 。
据此公式可知，首先求出 $A^{n-1} \, mod \, p$ ，然后用 $X_1$ 左乘，便可得到 $X_n$ ，而 $X_n$ 的第一个元素即为 $F_n$ 。注意：标红的公式，技巧在于使用了 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/

查看全文

http://www.mrgr.cn/news/62301.html