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

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

【题目来源】
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}。现在问题很简单,输入 nm,求 F_n 的前 n 项和 S_n \, mod \, m

【输入格式】
共一行,包含两个整数 nm

【输出格式】
输出前 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

相关文章:

  • 泷羽sec-安全见闻(9)
  • fmql之Linux以太网
  • IDE 使用技巧与插件推荐
  • 37.第二阶段x86游戏实战2-寻找万能按键call2
  • eclipse下载与安装(汉化教程)超详细
  • 【 C++ 】C++11的初步学习
  • 生成树协议——STP/RSTP/MSTP
  • Hello World for MCU
  • Rust 构建与测试自动化
  • 信息安全数学基础(37)有限生成交换群
  • CentOS9 Stream 设置禁用IPV6
  • sqlserver、达梦、mysql的差异
  • Android Handler消息机制(五)-HandlerThread完全解析
  • 电子信息-毕业设计题目(技术热点)
  • LeetCode 热题 100 回顾10
  • 实践甘肃数据挖掘挑战赛作物与杂草的智能识别,基于高精度YOLOv5全系列【n/s/m/l/x】参数模型开发构建田间低头作物杂草智能化检测识别模型
  • Android adb命令获取设备id
  • MyBatis版图书管理系统
  • 【渗透测试】01-信息收集-名词概念
  • 算法复杂度分析:深入剖析最好、最坏、平均、均摊时间复杂度
  • Linux学习_11
  • 勒索软件通过易受攻击的 Cyber​​Panel 实例攻击网络托管服务器
  • Linux学习_8
  • Swarm-LIO: Decentralized Swarm LiDAR-inertial Odometry论文翻译
  • 【模型学习之路】手写+分析bert
  • mysql使用DELIMITER,创建触发器、存储过程、存储函数