首页 > 代码库 > HDU 4686 Arc of Dream(矩阵快速幂)
HDU 4686 Arc of Dream(矩阵快速幂)
题目地址:HDU 4686
我去。。因为忘记把函数里的k定义成64位的,导致TLE了一晚上。。。晕。。
这题没什么技巧,就是根据公式构造就行。
代码如下:
#include <iostream> #include <cstdio> #include <string> #include <cstring> #include <stdlib.h> #include <math.h> #include <ctype.h> #include <queue> #include <map> #include <set> #include <algorithm> using namespace std; #define LL __int64 const LL mod=1e9+7; struct matrix { LL ma[8][8]; } init, res; matrix Mult(matrix x, matrix y) { int i, j, k; matrix tmp; memset(tmp.ma,0,sizeof(tmp.ma)); for(i=0; i<7; i++) { for(k=0; k<7; k++) { for(j=0; j<7; j++) { tmp.ma[i][j]=(tmp.ma[i][j]+x.ma[i][k]*y.ma[k][j])%mod; } } } return tmp; } matrix Pow(matrix x, LL k) { matrix tmp; int i, j; for(i=0; i<7; i++) for(j=0; j<7; j++) tmp.ma[i][j]=(i==j); while(k) { if(k&1) tmp=Mult(tmp,x); x=Mult(x,x); k>>=1; } return tmp; } int main() { LL k, ax, ay, bx, by, i, j, a0, b0; while(scanf("%I64d",&k)!=EOF) { scanf("%I64d%I64d%I64d%I64d%I64d%I64d",&a0,&ax,&ay,&b0,&bx,&by); if(k==0) { puts("0"); continue ; } memset(init.ma,0,sizeof(init.ma)); init.ma[0][0]=ax; init.ma[0][4]=1; init.ma[1][1]=bx; init.ma[1][5]=1; init.ma[2][0]=(ax*by)%mod;init.ma[2][1]=(ay*bx)%mod;init.ma[2][2]=(ax*bx)%mod;init.ma[2][3]=1; init.ma[3][3]=1; init.ma[4][4]=1; init.ma[5][5]=1; init.ma[6][0]=(ax*by)%mod;init.ma[6][1]=(ay*bx)%mod;init.ma[6][2]=(ax*bx)%mod;init.ma[6][3]=1;init.ma[6][6]=1; res=Pow(init,k-1); LL ans; ans=(a0*res.ma[6][0]+b0*res.ma[6][1]+a0*b0%mod*res.ma[6][2]+ay*by%mod*res.ma[6][3]+ay*res.ma[6][4]+by*res.ma[6][5]+a0*b0%mod*res.ma[6][6])%mod; printf("%I64d\n",ans); } return 0; }
HDU 4686 Arc of Dream(矩阵快速幂)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。