首页 > 代码库 > HDU 4686

HDU 4686

2024-07-21 00:39:19   217人阅读

再不能直视这道题，换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


联系
我们