HDU——4549M斐波那契数列(矩阵快速幂+快速幂+费马小定理)

时间:2022-09-15 19:54:55

M斐波那契数列

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 2598    Accepted Submission(s): 774

Problem Description
M斐波那契数列F[n]是一种整数数列,它的定义如下:

F[0] = a
F[1] = b
F[n] = F[n-1] * F[n-2] ( n > 1 )

现在给出a, b, n,你能求出F[n]的值吗?

 
Input
输入包含多组测试数据;
每组数据占一行,包含3个整数a, b, n( 0 <= a, b, n <= 10^9 )
 
Output
对每组测试数据请输出一个整数F[n],由于F[n]可能很大,你只需输出F[n]对1000000007取模后的值即可,每组数据输出一行。
 
Sample Input
0 1 0
6 10 2
 
Sample Output
0
60
 

水题一道
代码:
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<string>
#include<deque>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
#include<map>
using namespace std;
#define INF 0x3f3f3f3f
#define MM(x) memset(x,0,sizeof(x))
#define MMINF(x) memset(x,INF,sizeof(x))
typedef long long LL;
const double PI=acos(-1.0);
const LL mod=1000000007;
struct mat
{
LL pos[2][2];
mat(){MM(pos);}
};
mat operator*(const mat &a,const mat &b)
{
mat c;
for (int i=0; i<2; i++)
{
for (int j=0; j<2; j++)
{
for (int k=0; k<2; k++)
c.pos[i][j]+=(a.pos[i][k]*b.pos[k][j])%(mod-1);
}
}
return c;
}
mat operator^(mat a,LL b)
{
mat r;
for (int i=0; i<2; i++)
r.pos[i][i]=1;
while (b!=0)
{
if(b&1)
r=r*a;
a=a*a;
b>>=1;
}
return r;
}
LL qpow(LL a,LL b)
{
LL r=1;
a%=mod;
while (b)
{
if(b&1)
r=(r*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return r;
}
int main(void)
{
LL pa,pb;
LL a,b,c,n;
while (~scanf("%I64d%I64d%I64d",&a,&b,&n))
{
if(n==0)
printf("%I64d\n",a);
else if(n==1)
printf("%I64d\n",b);
else
{
mat t,one;
t.pos[0][0]=1;
t.pos[0][1]=1;
t.pos[1][0]=1;
one.pos[0][0]=1;
one.pos[1][0]=1;
t=t^(n-2);
one=t*one;
pa=one.pos[1][0]%(mod-1);
pb=one.pos[0][0]%(mod-1);
printf("%I64d\n",(qpow(a,pa)*qpow(b,pb))%mod);
}
}
return 0;
}

HDU——4549M斐波那契数列(矩阵快速幂+快速幂+费马小定理)的更多相关文章

  1. 斐波那契数列 矩阵乘法优化DP

    斐波那契数列 矩阵乘法优化DP 求\(f(n) \%1000000007​\),\(n\le 10^{18}​\) 矩阵乘法:\(i\times k\)的矩阵\(A\)乘\(k\times j\)的矩 ...

  2. hdu 4549 M斐波那契数列 矩阵快速幂&plus;欧拉定理

    M斐波那契数列 Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others) Problem ...

  3. 洛谷P1962 斐波那契数列 &vert;&vert; P1349 广义斐波那契数列&lbrack;矩阵乘法&rsqb;

    P1962 斐波那契数列 大家都知道,斐波那契数列是满足如下性质的一个数列: • f(1) = 1 • f(2) = 1 • f(n) = f(n-1) + f(n-2) (n ≥ 2 且 n 为整数 ...

  4. HDU4549 M斐波那契数列 矩阵快速幂&plus;欧拉函数&plus;欧拉定理

    M斐波那契数列 Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)Total Sub ...

  5. 51nod1242 斐波那契数列 矩阵快速幂

    1242 斐波那契数列的第N项 基准时间限制:1 秒 空间限制:131072 KB 分值: 0 难度:基础题 #include<stdio.h> #define mod 100000000 ...

  6. POJ3070 斐波那契数列 矩阵快速幂

    题目链接:http://poj.org/problem?id=3070 题意就是让你求斐波那契数列,不过n非常大,只能用logn的矩阵快速幂来做了 刚学完矩阵快速幂刷的水题,POJ不能用万能头文件是真 ...

  7. hdu4549 M斐波那契数列 矩阵快速幂&plus;快速幂

    M斐波那契数列F[n]是一种整数数列,它的定义如下: F[0] = aF[1] = bF[n] = F[n-1] * F[n-2] ( n > 1 ) 现在给出a, b, n,你能求出F[n]的 ...

  8. P1349 广义斐波那契数列&lpar;矩阵加速&rpar;

    P1349 广义斐波那契数列 题目描述 广义的斐波那契数列是指形如an=pan-1+qan-2的数列.今给定数列的两系数p和q,以及数列的最前两项a1和a2,另给出两个整数n和m,试求数列的第n项an ...

  9. 洛谷P1962 斐波那契数列&lpar;矩阵快速幂&rpar;

    题目背景 大家都知道,斐波那契数列是满足如下性质的一个数列: • f(1) = 1 • f(2) = 1 • f(n) = f(n-1) + f(n-2) (n ≥ 2 且 n 为整数) 题目描述 请 ...

随机推荐

  1. 用LoadRunner实现接口测试

    接口测试的两种方法 其实无论用那种测试方法,接口测试的原理是通过测试程序模拟客户端向服务器发送请求报文,服务器接收请求报文后对相应的报文做出处理然后再把应答报文发送给客户端,客户端接收应答报文这一个过 ...

  2. Postfix 发送邮件流程简析

      PostFix接受和转发邮件的说明 来源ip符合inet_interfaces,收件人域符合mydestination, Postfix将接收到本地. 来源ip符合inet_interfaces, ...

  3. CentOS生产机器禁止ROOT远程SSH登录

    方法一 很多站长拥有linux主机,不管是虚拟机还是实体机,一般我们远程连接的时候,都是用的ssh(SecureShell建立在应用层和传输层基础上的安全协议). 它默认的端口22,默认使用root也 ...

  4. hadoop集群监控工具ambari安装

    Apache Ambari是对Hadoop进行监控.管理和生命周期管理的基于网页的开源项目.它也是一个为Hortonworks数据平台选择管理组建的项目.Ambari支持管理的服务有: Apache ...

  5. solaris X86-64下一个ORACLE战斗11&period;2&period;0&period;3&period;8在一波折叠补丁

    solaris X86-64下一个ORACLE战斗11.2.0.3.8补丁: 正确的步骤: 1.BUG6880880 .OPATCH补丁 2.BUG16902043.11.2.0.3.8补丁 情感是练 ...

  6. URL模块之parse方法

    url.parse(urlString , boolean , boolean) parse这个方法可以将一个url的字符串解析并返回一个url的对象. 参数: urlString指传入一个url地址 ...

  7. Firefox 多行标签的解决方案分享

    更新了 Quantum 以后 TabMixPlus 就不能用了,我最中意的多行标签也没了,捣鼓了一下终于重新回来了. 指南: https://discourse.mozilla.org/t/tabs- ...

  8. MongoDB的aggregate聚合

    聚合框架中常用的几个操作: $project:修改输入文档的结构.可以用来重命名.增加或删除域,也可以用于创建计算结果以及嵌套文档.(显示的列,相当遇sql 的) $match:用于过滤数据,只输出符 ...

  9. BZOJ2017&lbrack;USACO 2009 Nov Silver 1&period;A Coin Game&rsqb;——DP&plus;博弈论

    题目描述 农夫约翰的奶牛喜欢玩硬币游戏,因此他发明了一种称为“Xoinc”的两人硬币游戏. 初始时,一个有N(5 <= N <= 2,000)枚硬币的堆栈放在地上,从堆顶数起的第I枚硬币的 ...

  10. 详解php多人开发环境原理

    作为一名php开发人员,有时候一个项目或一个功能我们不能独自完成,就像当一个仓库开发人员大于1,20人的时候,每个人可能开发不同的模块和功能,用代码版本控制工具比如 git 开不同的分支,流程大概是先 ...