首页 > 代码库 > 残（矩阵快速幂）
残（矩阵快速幂）
定义f（x）为斐波那契数列第x项
输出f（f(x)）%1000000007；
x<=10^100;
思路：
矩阵快速幂+各种神奇的模；
来，上代码：
#include <cmath>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define mod 1000000007LL#define mod2 2000000016LL#define mod3 6000000048LLusing namespace std;struct MatrixType { long long c[3][3];};long long dis[95];char Cget;inline void in(long long &now){ now=0,Cget=getchar(); while(Cget>‘9‘||Cget<‘0‘) Cget=getchar(); while(Cget>=‘0‘&&Cget<=‘9‘) { now=now*10+Cget-‘0‘; Cget=getchar(); }}long long f1(long long mi){ long long now=1; struct MatrixType res,mul;// mul.sta(),res.st(); mul.c[1][1]=mul.c[1][2]=mul.c[2][1]=res.c[1][2]=1; mul.c[2][2]=res.c[1][1]=res.c[2][1]=res.c[2][2]=0; while(now<=mi) { if(now&mi) { struct MatrixType pos; pos.c[1][1]=0; pos.c[1][2]=0; pos.c[2][2]=0; pos.c[2][1]=0; for(int i=1;i<=2;i++) { for(int j=1;j<=2;j++) { for(int v=1;v<=2;v++) { pos.c[i][j]=(pos.c[i][j]+res.c[i][v]*mul.c[v][j]%mod2)%mod2; } } } res=pos; } struct MatrixType poxs; poxs.c[1][1]=0; poxs.c[1][2]=0; poxs.c[2][2]=0; poxs.c[2][1]=0; for(int i=1;i<=2;i++) { for(int j=1;j<=2;j++) { for(int v=1;v<=2;v++) { poxs.c[i][j]=(poxs.c[i][j]+mul.c[i][v]*mul.c[v][j]%mod2)%mod2; } } } mul=poxs,now<<=1; } return res.c[1][1];}long long f(long long mi){ long long now=1; struct MatrixType res,mul;// mul.sta(),res.st(); mul.c[1][1]=mul.c[1][2]=mul.c[2][1]=res.c[1][2]=1; mul.c[2][2]=res.c[1][1]=res.c[2][1]=res.c[2][2]=0; while(now<=mi) { if(now&mi) { struct MatrixType pos; pos.c[1][1]=0; pos.c[1][2]=0; pos.c[2][2]=0; pos.c[2][1]=0; for(int i=1;i<=2;i++) { for(int j=1;j<=2;j++) { for(int v=1;v<=2;v++) { pos.c[i][j]=(pos.c[i][j]+res.c[i][v]*mul.c[v][j]%mod)%mod; } } } res=pos; } struct MatrixType poxs; poxs.c[1][1]=0; poxs.c[1][2]=0; poxs.c[2][2]=0; poxs.c[2][1]=0; for(int i=1;i<=2;i++) { for(int j=1;j<=2;j++) { for(int v=1;v<=2;v++) { poxs.c[i][j]=(poxs.c[i][j]+mul.c[i][v]*mul.c[v][j]%mod)%mod; } } } mul=poxs,now<<=1; } return res.c[1][1];}int main(){ freopen("na.in","r",stdin); freopen("na.out","w",stdout); long long t,len; in(t);char ch[401];// dis[1]=1;// for(int i=2;i<=90;i++) dis[i]=dis[i-1]+dis[i-2]; while(t--) { long long x=0; scanf("%s",ch),len=strlen(ch); for(int i=len-1;i>=0;i--) x=(x*10+ch[i]-‘0‘)%mod3; cout<<f(f1(x))%mod<<endl; } fclose(stdin),fclose(stdout); return 0;}
残（矩阵快速幂）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。