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?
矩阵快速幂
1 #include<stdio.h>
2 #include<string.h>
3 typedef long long ll;
4 const int mod=1000000007;
5
6 struct mat{
7 int r,c;
8 ll m[6][6];
9 void clear(){
10 for(int i=1;i<=r;i++)memset(m[i],0,sizeof(m[i]));
11 }
12 };
13
14 mat MatMul(mat &m1,mat &m2){
15 mat tmp;
16 tmp.r=m1.r;
17 tmp.c=m2.c;
18 int i,j,k;
19 for(i=1;i<=tmp.r;i++){
20 for(j=1;j<=tmp.c;j++){
21 ll t=0;
22 for(k=1;k<=m1.c;k++){
23 t=(t+(m1.m[i][k]*m2.m[k][j])%mod)%mod;
24 }
25 tmp.m[i][j]=t;
26 }
27 }
28 return tmp;
29 }
30
31 mat MatQP(mat &a,ll n){
32 mat ans,tmp=a;
33 ans.r=ans.c=a.r;
34 memset(ans.m,0,sizeof(ans.m));
35 for(int i=1;i<=ans.r;i++){
36 ans.m[i][i]=1;
37 }
38 while(n){
39 if(n&1)ans=MatMul(ans,tmp);
40 n>>=1;
41 tmp=MatMul(tmp,tmp);
42 }
43 return ans;
44 }
45
46 int main(){
47 ll n;
48 mat a;
49 a.r=5,a.c=1;
50 mat tmp;
51 tmp.c=tmp.r=5;
52 ll a0,b0,ax,ay,bx,by;
53 while(scanf("%lld",&n)!=EOF){
54 scanf("%lld%lld%lld%lld%lld%lld",&a0,&ax,&ay,&b0,&bx,&by);
55 a0%=mod;
56 ax%=mod;
57 ay%=mod;
58 b0%=mod;
59 bx%=mod;
60 by%=mod;
61 a.clear();
62 a.m[1][1]=0;
63 a.m[2][1]=(a0*b0)%mod;
64 a.m[3][1]=b0;
65 a.m[4][1]=a0;
66 a.m[5][1]=1;
67 tmp.clear();
68 tmp.m[1][1]=tmp.m[1][2]=tmp.m[5][5]=1;
69 tmp.m[2][2]=(ax*bx)%mod;
70 tmp.m[2][3]=(ay*bx)%mod;
71 tmp.m[2][4]=(ax*by)%mod;
72 tmp.m[2][5]=(ay*by)%mod;
73 tmp.m[3][3]=bx;
74 tmp.m[3][5]=by;
75 tmp.m[4][4]=ax;
76 tmp.m[4][5]=ay;
77 // tmp.m[1][3]=tmp.m[1][4]=tmp.m[1][5]=tmp.m[2][1]=tmp.m[3][1]=tmp.m[3][2]=tmp.m[3][4]=tmp.m[4][1]=tmp.m[4][2]=tmp.m[4][3]=tmp.m[5][1]=tmp.m[5][2]=tmp.m[5][3]=tmp.m[5][4]=0;
78 tmp=MatQP(tmp,n);
79 a=MatMul(tmp,a);
80 printf("%lld
",a.m[1][1]);
81 }
82 return 0;
83 }