2015
09-17

# Arc of Dream

An Arc of Dream is a curve defined by following function:

where
a0 = A0
ai = ai-1*AX+AY
b0 = B0
bi = bi-1*BX+BY
What is the value of AoD(N) modulo 1,000,000,007?

There are multiple test cases. Process to the End of File.
Each test case contains 7 nonnegative integers as follows:
N
A0 AX AY
B0 BX BY
N is no more than 1018, and all the other integers are no more than 2×109.

There are multiple test cases. Process to the End of File.
Each test case contains 7 nonnegative integers as follows:
N
A0 AX AY
B0 BX BY
N is no more than 1018, and all the other integers are no more than 2×109.

1
1 2 3
4 5 6
2
1 2 3
4 5 6
3
1 2 3
4 5 6

4
134
1902

ai = ai-1*AX+AY
b0 = B0
bi = bi-1*BX+BY

n<=10^18.

=(ai-1 * bi-1 *ax*bx)+(ai-1 *ax*by)+(bi-1 *bx*ay)+(ay*by)

s(n)=sum(ai*bi),i=0,1,…n

【f(n-1),a(n-1),b(n-1),1,s(n-2)】*A=【f(n),a(n),b(n),1,s(n-1)】

=【p*f(n-1)+q*a(n-1)+r*b(n-1)+s, a(n-1)*ax+ay, b(n-1)*bx+by, 1, s(n-2)+f(n-1)】

axby   ax   0   0   0

aybx    0   bx  0   0

ayay   ay  by   1   0

0         0    0    0   1 】

b(1)=b0*bx+by, s(0)=a0*b0

AC代码如下：

 #include<stdio.h>
#include<string.h>
//#define LL __int64
#define LL long long
#define M 1000000007
struct Matrix
{
LL a[6][6];
}origin,res,tmp,A,ans;
int n;
Matrix mul(Matrix x,Matrix y)
{
int i,j,k;
memset(tmp.a,0,sizeof(tmp.a));
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
for(k=1;k<=n;k++)
{
tmp.a[i][j]+=(x.a[i][k]*y.a[k][j])%M;
tmp.a[i][j]%=M;
}
return tmp;
}
void quickpow(LL k)
{
int i;
memset(res.a,0,sizeof(res.a));
for(i=1;i<=n;i++)
res.a[i][i]=1;
while(k)
{
if(k&1)
res=mul(res,A);
A=mul(A,A);
k>>=1;
}
}
int main()
{
LL N,a0,ax,ay,b0,bx,by;
LL f1,a1,b1,s0;
//    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)
{
if(N==0)
{
printf("0\n");
continue;
}
a1=(a0*ax+ay)%M;
b1=(b0*bx+by)%M;
f1=(a1*b1)%M;
s0=(a0*b0)%M;
n=5;
memset(origin.a,0,sizeof(origin.a));
origin.a[1][1]=f1;
origin.a[1][2]=a1;
origin.a[1][3]=b1;
origin.a[1][4]=1;
origin.a[1][5]=s0;
memset(A.a,0,sizeof(A.a));
A.a[1][1]=(ax*bx)%M;
A.a[1][5]=1;
A.a[2][1]=(ax*by)%M;
A.a[2][2]=ax%M;
A.a[3][1]=(ay*bx)%M;
A.a[3][3]=bx%M;
A.a[4][1]=(ay*by)%M;
A.a[4][2]=ay%M;
A.a[4][3]=by%M;
A.a[4][4]=1;
A.a[5][5]=1;

quickpow(N-1);
ans=mul(origin,res);
//    printf("%I64d\n",ans.a[1][5]);
printf("%lld\n",ans.a[1][5]);
}
return 0;
}