首页 > 代码库 > HDU 4686
HDU 4686
再不能直视这道题,换INT64就过了。。。。。。。
同样可以使用矩阵的方法。构造1*5的
D[N],a[n],b[n],a【n】*b[n],1
接着你应该就会了。
#include <iostream>#include <cstdio>#include <algorithm>#define LL __int64using namespace std;const LL Mod=1000000007;struct Matrax{ LL m[6][6];};LL N,A0, AX, AY,B0, BX, BY;Matrax a,per;void initial(){ for(int i=0;i<5;i++){ for(int j=0;j<5;j++) a.m[i][j]=per.m[i][j]=0; } for(int i=0;i<5;i++) per.m[i][i]=1; a.m[0][0]=a.m[3][0]=1; a.m[1][1]=(AX); a.m[4][1]=(AY); a.m[2][2]=(BX); a.m[4][2]=(BY); a.m[1][3]=(AX* BY)%Mod; a.m[2][3]=(AY* BX)%Mod; a.m[3][3]= (AX* BX)%Mod; a.m[4][3]=(AY* BY)%Mod; a.m[4][4]=1;}Matrax multi(Matrax a,Matrax b){ Matrax c; for(int i=0;i<5;i++){ for(int j=0;j<5;j++){ c.m[i][j]=0; for(int k=0;k<5;k++) c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%Mod; } } return c;}Matrax quick(LL k){ Matrax ans=per,p=a; while(k){ if(k&1){ ans=multi(ans,p); } k>>=1; p=multi(p,p); } return ans;}LL ts[5];int main(){ while(scanf("%I64d%I64d%I64d%I64d%I64d%I64d%I64d",&N,&A0,&AX,&AY,&B0,&BX,&BY)!=EOF){// while(scanf("%lld%lld%lld%lld%lld%lld%lld",&N,&A0,&AX,&AY,&B0,&BX,&BY)!=EOF){ LL tp=0; if(N==0){ printf("0\n"); continue; } A0%=Mod; B0%=Mod; AX%=Mod; AY%=Mod; BX%=Mod; BY%=Mod; ts[0]=A0*B0%Mod; ts[1]=(A0*AX+AY)%Mod; ts[2]=(B0*BX+BY)%Mod; ts[3]=(ts[1]*ts[2])%Mod; ts[4]=1; initial(); Matrax ans=quick(N-1); for(int i=0;i<5;i++){ tp=(tp+ts[i]*ans.m[i][0])%Mod; } // printf("%lld\n",tp%Mod); printf("%I64d\n",tp%Mod); } return 0;}
HDU 4686
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。