首页 > 代码库 > hdu 3326 Another kind of Fibonacci (矩阵构造)
hdu 3326 Another kind of Fibonacci (矩阵构造)
题目大意:
描述了另外一种斐波那契
F[n] = x*F[n-1] + y*F[n-2];
求segma(F[i]^2);
思路分析:
构造矩阵的详细 请戳我
构造矩阵可以得到
中间矩阵为
1 1 00
0 x^2 y^2 2*x*y
0 1 0 0
0 x 0 y
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #define N 30 typedef long long LL; using namespace std; const LL mod = 10007; struct matrix { int a[4][4]; }origin; matrix multiply(matrix x,matrix y) { matrix temp; memset(temp.a,0,sizeof(temp.a)); for(int i=0;i<4;i++) { for(int j=0;j<4;j++) { for(int k=0;k<4;k++) { temp.a[i][j]+=x.a[i][k]*y.a[k][j]; temp.a[i][j]=(temp.a[i][j])%mod; } } } return temp; } matrix matmod(matrix a,LL k) { matrix res; memset(res.a,0,sizeof res.a); for(int i=0;i<4;i++)res.a[i][i]=1; while(k) { if(k&1) res=multiply(res,a); k>>=1; a=multiply(a,a); } return res; } int main() { int n,x,y; while(scanf("%d%d%d",&n,&x,&y)!=EOF) { matrix st; x%=mod; y%=mod; st.a[0][0]=st.a[0][1]=1; st.a[0][2]=st.a[0][3]=0; st.a[1][0]=0; st.a[1][1]=(x*x)%mod; st.a[1][2]=(y*y)%mod; st.a[1][3]=(2*x*y)%mod; st.a[2][0]=st.a[2][2]=st.a[2][3]=0; st.a[2][1]=1; st.a[3][0]=st.a[3][2]=0; st.a[3][1]=x%mod; st.a[3][3]=y%mod; matrix end = matmod(st,n); int ans=0; for(int i=0;i<4;i++) { ans+=end.a[0][i]; ans%=mod; } printf("%d\n",ans%mod); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。