首页 > 代码库 > [矩阵快速幂] hdu 3936 FIB Query
[矩阵快速幂] hdu 3936 FIB Query
题意:
求定义y(x)=4*x-1
给L、R求 fib(y(L))~fib(y(R))的和
思路:
和之前做的一道题类似。
定于Fib为
1 1
1 0
我们的第一项就是x=1时的 就是Fib^3
然后下一项其实就是fib(3+4)=Fib^3*Fib^4
所以递推矩阵就是Fib^4
然后求和利用快速的求法
设
Fib E
0 E
这样运算N次右上角的矩阵就是我们要的和的矩阵了
然后就是答案了~!
代码:
#include"cstdlib" #include"cstdio" #include"cstring" #include"cmath" #include"queue" #include"algorithm" #include"iostream" using namespace std; #define ll __int64 __int64 mod=1000000007; struct matrix { __int64 mat[5][5]; }; matrix matadd(matrix a,matrix b,int n,int m) { int i,j; matrix c; memset(c.mat,0,sizeof(c.mat)); for(i=0; i<n; i++) for(j=0; j<n; j++) c.mat[i][j]=(a.mat[i][j]+b.mat[i][j])%m; return c; } matrix matmul(matrix a,matrix b,int n,int m) { int i,j,k; matrix c; memset(c.mat,0,sizeof(c.mat)); for(i=0; i<n; i++) { for(j=0; j<n; j++) { for(k=0; k<n; k++) { c.mat[i][j]+=a.mat[i][k]*b.mat[k][j]; c.mat[i][j]%=m; } } } return c; } matrix matpow(matrix a,__int64 k,int n,int m) { matrix b; int i; memset(b.mat,0,sizeof(b.mat)); for(i=0; i<n; i++) b.mat[i][i]=1; while(k) { if(k&1) b=matmul(a,b,n,m); a=matmul(a,a,n,m); k>>=1; } return b; } matrix matsum(matrix a,__int64 k,int n,int m) { if(k<=0) return matpow(a,0,n,m); int x=(k+1)/2; matrix b,ans; b=matsum(a,x-1,n,m); ans=matadd(b,matmul(b,matpow(a,x,n,m),n,m),n,m); if(k%2==0) ans=matadd(ans,matpow(a,k,n,m),n,m); return ans; } ll solve(ll x) { x--; if(x<0) return 0; matrix a,b,c,ans; memset(a.mat,0,sizeof(a.mat)); memset(b.mat,0,sizeof(b.mat)); memset(c.mat,0,sizeof(c.mat)); c.mat[0][0]=c.mat[0][1]=c.mat[1][0]=1; a=matpow(c,3,2,mod); b=matpow(c,4,2,mod); b.mat[0][2]=b.mat[1][3]=b.mat[2][2]=b.mat[3][3]=1; ans=matpow(b,x+1,4,mod); b.mat[0][0]=ans.mat[0][2]; b.mat[0][1]=ans.mat[0][3]; b.mat[1][0]=ans.mat[1][2]; b.mat[1][1]=ans.mat[1][3]; ans=matmul(a,b,2,mod); return ans.mat[0][1]; } int main() { int t; cin>>t; while(t--) { ll x,y; scanf("%I64d%I64d",&x,&y); ll ans=solve(y)-solve(x-1); ans=(ans%mod+mod)%mod; printf("%I64d\n",ans); } return 0; }
[矩阵快速幂] hdu 3936 FIB Query
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。