HDU 1588 Gauss Fibonacci

HDU 1588 Gauss Fibonacci

​​， f(1)=1 ，f[n]=f[n-1]+f[n-2]

求解：

因为斐波那契存在关系：

有：

所以：

换元表示：

接下来处理，矩阵快速幂和等比数列。

关于等比数列：

即递归处理。

#include #include using namespace std;typedef long long LL;LL k,b,n,M;struct matrix{ LL m[2][2];};matrix A={1,1,1,0};matrix I={1,0,0,1};matrix multi(matrix a,matrix b){ matrix ans; for(int i=0;i<2;i++){ for(int j=0;j<2;j++){ ans.m[i][j]=0; for(int k=0;k<2;k++){ ans.m[i][j]=(ans.m[i][j]+a.m[i][k]*b.m[k][j]%M)%M; } } } return ans;}matrix quick(matrix a,int n){ matrix ans=I,temp=a; if(n==-1){ ans.m[0][0]=0; ans.m[0][1]=1; ans.m[1][0]=1; ans.m[1][1]=-1; return ans; } while(n>0){ if(n&1) ans=multi(ans,temp); temp=multi(temp,temp); n>>=1; } return ans;}matrix add(matrix a,matrix b){ matrix ans; for(int i=0;i<2;i++){ for(int j=0;j<2;j++){ ans.m[i][j]=(a.m[i][j]+b.m[i][j])%M; } } return ans;}matrix selfquick(matrix t,int n){ if(n==0) return I; if(n&1){ matrix mid=quick(t,n/2+1); return multi(add(mid,I),selfquick(t,n/2)); //尽量少用递归 } else { matrix mid=quick(t,n/2); matrix miadd=quick(t,n/2+1); matrix q1=multi(add(miadd,I),selfquick(t,n/2-1)); return add(q1,quick(t,n/2)); }}int main(int argc, char *argv[]) { while(~scanf("%lld%lld%lld%lld",&k,&b,&n,&M)){ matrix t1=quick(A,b-1),t2=quick(A,k); t2=selfquick(t2,n-1); matrix ans=multi(t1,t2); printf("%lld\n",ans.m[0][0]); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。