首页 > 代码库 > CodeForces 450B （矩阵快速幂模板题+负数取模）
CodeForces 450B （矩阵快速幂模板题+负数取模）
题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=51919
题目大意：斐波那契数列推导。给定前f1，f2，推出指定第N项。注意负数取模的方式：-1%(10^9+7)=10^9+6。
解题思路：
首先解出快速幂矩阵。以f3为例。 [f2] * [1 -1] = [f2-f1]=[f3] (幂1次）
[f1] * [1 0] [f2] [f2]
于是fn=[f2] *[1 -1]^(n-2)
[f1] [1 0]
注意一下负数取模。ans=（ans%mod+mod)%mod。
#include "cstdio"#include "cstring"#define LL long long#define mod 1000000007struct Matrix{ LL mat[2][2]; Matrix() {memset(mat,0,sizeof(mat));} Matrix(int a,int b,int c,int d) {mat[0][0]=a;mat[0][1]=b;mat[1][0]=c;mat[1][1]=d;}};Matrix operator * (Matrix a,Matrix b){ Matrix ret; for(int i=0;i<2;i++) for(int j=0;j<2;j++) { ret.mat[i][j]=0; for(int k=0;k<2;k++) ret.mat[i][j]+=(a.mat[i][k]*b.mat[k][j])%mod; } return ret;}Matrix operator ^ (Matrix a,int n){ Matrix ret,base=a; ret.mat[0][0]=ret.mat[1][1]=1; while(n) { if(n&1) ret=ret*base; base=base*base; n>>=1; } return ret;}int main(){ LL a,b,n; while(scanf("%I64d%I64d%I64d",&a,&b,&n)!=EOF) { if(n==1) printf("%I64d\n",((a%mod)+mod)%mod); else if(n==2) printf("%I64d\n",((b%mod)+mod)%mod); else { Matrix x(1,-1,1,0),tt; tt=x^(n-2); LL ans=a*tt.mat[0][1]+b*tt.mat[0][0]; printf("%I64d\n",((ans%mod)+mod)%mod); } }}
| 2824556 | neopenx | CodeForces 450B | Accepted | 0 KB | 78 ms | GNU C++ 4.6 | 1263 B | 2014-10-07 02:08:58 |
CodeForces 450B （矩阵快速幂模板题+负数取模）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。