首页 > 代码库 > Water Problem(快速幂)
Water Problem(快速幂)
题目大意:原题链接
这几天的题有时间再总结......
#include<cstdio> #include<cstring> typedef long long ll; const ll mod=1e9+7; long long f[10]; int temp[4]={0,1,0,-1}; struct Mat { ll mat[4][4]; }res; Mat Mult(Mat a,Mat b) { Mat c; memset(c.mat,0,sizeof(c.mat)); for(int i=0;i<4;i++) for(int j=0;j<4;j++) for(int k=0;k<4;k++) c.mat[i][j]=(c.mat[i][j]+a.mat[i][k]*b.mat[k][j])%mod; return c; } Mat QMult(Mat a,ll b) { Mat t; for(int i=0;i<4;i++){ for(int j=0;j<4;j++){ t.mat[i][j]=i==j; } } while(b){ if(b&1) t=Mult(t,a);//注意方向,t在前,a在后 a=Mult(a,a); b>>=1; } return t; } int main() { int a,b,n; while(scanf("%d%d%d",&a,&b,&n)!=EOF){ f[1]=a,f[2]=b; for(int i=3;i<=5;i++) f[i]=f[i-1]+f[i-2]+temp[(i-1)%4]; if(n<=5){ printf("%d\n",f[n]); continue; } res.mat[0][0]=res.mat[0][2]=res.mat[0][3]=1; res.mat[1][0]=res.mat[2][1]=res.mat[3][2]=1; Mat ans=QMult(res,n-5); int anss=(ans.mat[0][0]*f[5]%mod)+(ans.mat[0][1]*f[4]%mod); anss=anss+(ans.mat[0][2]*f[3]%mod)+(ans.mat[0][3]*f[2]%mod); printf("%d\n",anss%mod); } }
#include<cstdio> #include<cstring> typedef long long ll; const ll mod=1e9+7; long long f[10]; int temp[4]={0,1,0,-1}; struct Mat { ll mat[4][4]; }res; Mat Mult(Mat a,Mat b) { Mat c; memset(c.mat,0,sizeof(c.mat)); for(int i=0;i<4;i++) for(int j=0;j<4;j++) for(int k=0;k<4;k++) c.mat[i][j]=(c.mat[i][j]+a.mat[i][k]*b.mat[k][j])%mod; return c; } Mat QMult(Mat a,ll b) { Mat t; memset(t.mat,0,sizeof(t.mat)); t.mat[0][0]=t.mat[0][2]=t.mat[0][3]=1; t.mat[1][0]=t.mat[2][1]=t.mat[3][2]=1; while(b){ if(b&1) a=Mult(t,a); t=Mult(t,t); b>>=1; } return a; } int main() { int a,b,n; while(scanf("%d%d%d",&a,&b,&n)!=EOF){ f[1]=a,f[2]=b; for(int i=3;i<=5;i++) f[i]=f[i-1]+f[i-2]+temp[(i-1)%4]; if(n<=5){ printf("%d\n",f[n]); continue; } res.mat[0][0]=f[5],res.mat[1][0]=f[4]; res.mat[2][0]=f[3],res.mat[3][0]=f[2]; Mat ans=QMult(res,n-5); printf("%d\n",ans.mat[0][0]%mod); } }
Water Problem(快速幂)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。