首页 > 代码库 > 洛谷P1962 斐波那契数列 || P1349 广义斐波那契数列[矩阵乘法]
洛谷P1962 斐波那契数列 || P1349 广义斐波那契数列[矩阵乘法]
P1962 斐波那契数列
大家都知道，斐波那契数列是满足如下性质的一个数列：
• f(1) = 1
• f(2) = 1
• f(n) = f(n-1) + f(n-2) (n ≥ 2 且 n 为整数)
题目描述
请你求出 f(n) mod 1000000007 的值。
输入输出格式
输入格式：
·第 1 行：一个整数 n
输出格式：
第 1 行： f(n) mod 1000000007 的值
输入输出样例
输入样例#1：
5
输出样例#1：
5
输入样例#2：
10
输出样例#2：
55
说明
对于 60% 的数据： n ≤ 92
对于 100% 的数据： n在long long(INT64)范围内。
1 1
1 0
fn+1 fn
fn fn-1
注意n的范围
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>using namespace std;typedef long long ll;const int MOD=1e9+7;ll n;struct mat{ ll m[3][3]; mat(){memset(m,0,sizeof(m));}}im,f;void init(){ im.m[1][1]=im.m[2][2]=1; f.m[1][1]=f.m[1][2]=f.m[2][1]=1;}mat mul(mat &a,mat &b){ mat c; for(int i=1;i<=2;i++) for(int k=1;k<=2;k++) if(a.m[i][k]) for(int j=1;j<=2;j++) c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j]%MOD)%MOD; return c;}int main(){ scanf("%lld",&n); init(); mat ans=im; for(;n;n>>=1,f=mul(f,f)) if(n&1) ans=mul(ans,f); printf("%d",ans.m[1][2]);}
P1349 广义斐波那契数列
题目描述
广义的斐波那契数列是指形如an=p*an-1+q*an-2的数列。今给定数列的两系数p和q，以及数列的最前两项a1和a2，另给出两个整数n和m，试求数列的第n项an除以m的余数。
输入输出格式
输入格式：
输入包含一行6个整数。依次是p,q,a1,a2,n,m，其中在p,q,a1,a2整数范围内，n和m在长整数范围内。
输出格式：
输出包含一行一个整数，即an除以m的余数。
输入输出样例
输入样例#1：
1 1 1 1 10 7
输出样例#1：
6
说明
数列第10项是55，除以7的余数为6。
构造矩阵
p q
1 0
求它的n-2次幂，再乘
a2
a1
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>using namespace std;typedef long long ll;ll p,q,a1,a2,n,MOD;struct mat{ int r,c; ll m[3][3]; mat(){r=c=2;memset(m,0,sizeof(m));}}im,f;void init(){ im.m[1][1]=im.m[2][2]=1; f.m[1][1]=p;f.m[1][2]=q;f.m[2][1]=1;}mat mul(mat &a,mat &b){//printf("p\n"); mat c; for(int i=1;i<=a.r;i++) for(int k=1;k<=a.c;k++) if(a.m[i][k]) for(int j=1;j<=b.c;j++) c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j]%MOD)%MOD; return c;}int main(){ scanf("%d%d%d%d%lld%lld",&p,&q,&a1,&a2,&n,&MOD); init();n-=2; mat ans=im; for(;n;n>>=1,f=mul(f,f)) if(n&1) ans=mul(ans,f); //printf("a %d %d %d %d\n",ans.m[1][1],ans.m[1][2],ans.m[2][1],ans.m[2][2]); mat a; a.r=2;a.c=1; a.m[1][1]=a2;a.m[2][1]=a1; a=mul(ans,a); printf("%d",a.m[1][1]%MOD);}
PS
gcd(fn,fm)=f(gcd(n,m))
洛谷P1962 斐波那契数列 || P1349 广义斐波那契数列[矩阵乘法]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。