hdu 4686 Arc of Dream
矩阵快速幂：
1,A0%N,B0%N,A0*B0%N,A0*B0%N;
1,AY%N,BY%N,AY*BY%N,AY*BY%N;
AX%N, 0,AX*BY%N,AX*BY%N;
BX%N,BX*AY%N,BX*AY%N;
AX*BX%N,AX*BX%N;
1;
#include <cstdio>
#include <cstring>
#define N 1000000007
#define LL long long
struct matrix
{
LL num[5][5];
};
matrix p,m,q;
matrix cal(matrix x,matrix y)
{
for(int i=0; i<5; ++i)
for(int j=0; j<5; ++j)
{
q.num[i][j]=0;
for(int k=0; k<5; ++k)
q.num[i][j]=(q.num[i][j]+x.num[i][k]*y.num[k][j]%N)%N;
}
return q;
}
void solve(LL n)
{
while(n)
{
if(n&1) m=cal(m,p);
n>>=1;
p=cal(p,p);
}
}
int main()
{
// freopen("in.txt","r",stdin);
LL AX,AY,A0,BX,BY,B0,n;
while(scanf("%I64d%I64d%I64d%I64d%I64d%I64d%I64d",&n,&A0,&AX,&AY,&B0,&BX,&BY)!=EOF)
{
if(n==0)
{
printf("0
");
continue;
}
memset(m.num,0,sizeof(m.num));
memset(p.num,0,sizeof(p.num));
m.num[0][0]=1,m.num[0][1]=A0%N,m.num[0][2]=B0%N,m.num[0][3]=A0*B0%N,m.num[0][4]=A0*B0%N;
p.num[0][0]=1,p.num[0][1]=AY%N,p.num[0][2]=BY%N,p.num[0][3]=AY*BY%N,p.num[0][4]=AY*BY%N;
p.num[1][1]=AX%N,p.num[1][3]=AX*BY%N,p.num[1][4]=AX*BY%N;
p.num[2][2]=BX%N,p.num[2][3]=BX*AY%N,p.num[2][4]=BX*AY%N;
p.num[3][3]=AX*BX%N,p.num[3][4]=AX*BX%N;
p.num[4][4]=1;
solve(n-1);
printf("%I64d
",m.num[0][4]);
}
return 0;
}