Time Limit: 2000/2000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others) Total Submission(s): 2010 Accepted Submission(s): 643
Problem Description
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?
Input
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.
Output
For each test case, output AoD(N) modulo 1,000,000,007.
Sample Input
1 1 2 3 4 5 6 2 1 2 3 4 5 6 3 1 2 3 4 5 6
Sample Output
4 134 1902
Author
Zejun Wu (watashi)
Source
2013 Multi-University Training Contest 9
这道题的分析,其实应该这样分析:
我们看到这么个式子
然后我们知道ai=ai-1*AX+AY ; bi=bi-1*BX+BY;
ai*bi =AXBX*ai-1*bi-1+AXBY*ai-1+BXAY*bi-1+AY*BY;
对于这样一个式子,我们不妨构造这样一个矩阵......
如:
|ai*bi| |AX*BX , AXBY , BXAY , AYBY, 0 |^n-1 | ai-1*ai-1 |
| ai | | 0 , AX , 0 , AY , 0 | | ai-1 |
| bi | = | 0 , 0 , BX , BY , 0 | * | bi-1 |
| 1 | | 0 , 0 , 0 , 1 , 0 | | 1 |
| sn | | AXBX , AXBY, BXAY, AYBY, 1 | | sn-1 |
然后就是快速矩阵...
1 #define LOCAL
2 #include<cstdio>
3 #include<cstring>
4 #define LL __int64
5 using namespace std;
6
7 const LL mod=1000000007;
8
9 struct node
10 {
11 LL mat[5][5];
12 void init(int v){
13 for(int i=0;i<5;i++){
14 for(int j=0;j<5;j++)
15 if(i==j)
16 mat[i][j]=v;
17 else
18 mat[i][j]=0;
19 }
20 }
21 };
22
23
24 LL AO,BO,AX,AY,BX,BY,n;
25 node ans,cc;
26
27 void init(node &a)
28 {
29 a.mat[4][0]=a.mat[0][0]=(AX*BX)%mod;
30 a.mat[4][1]=a.mat[0][1]=(AX*BY)%mod;
31 a.mat[4][2]=a.mat[0][2]=(BX*AY)%mod;
32 a.mat[4][3]=a.mat[0][3]=(AY*BY)%mod;
33 a.mat[1][0]=a.mat[1][3]=a.mat[1][4]=a.mat[0][4]=0;
34 a.mat[2][0]=a.mat[2][1]=a.mat[2][4]=0;
35 a.mat[3][0]=a.mat[3][1]=a.mat[3][2]=a.mat[3][4]=0;
36 a.mat[3][3]=a.mat[4][4]=1;
37 a.mat[1][1]=AX;
38 a.mat[1][3]=AY;
39 a.mat[2][2]=BX;
40 a.mat[2][3]=BY;
41 }
42
43 void Matrix(node &a, node &b)
44 {
45 node c;
46 c.init(0);
47 for(int i=0;i<5;i++)
48 {
49 for(int j=0;j<5;j++)
50 {
51 for(int k=0;k<5;k++)
52 {
53 c.mat[i][j]=(c.mat[i][j]+a.mat[i][k]*b.mat[k][j])%mod;
54 }
55 }
56 }
57
58 for(int i=0;i<5;i++)
59 {
60 for(int j=0;j<5;j++)
61 {
62 a.mat[i][j]=c.mat[i][j];
63 }
64 }
65 }
66
67 void pow(node &a,LL w )
68 {
69 while(w>0)
70 {
71 if(w&1) Matrix(ans,a);
72 w>>=1L;
73 if(w==0)break;
74 Matrix(a,a);
75 }
76 }
77
78 int main()
79 {
80 LL sab;
81 #ifdef LOCAL
82 freopen("test.in","r",stdin);
83 #endif
84 while(scanf("%I64d",&n)!=EOF)
85 {
86 scanf("%I64d%I64d%I64d",&AO,&AX,&AY);
87 scanf("%I64d%I64d%I64d",&BO,&BX,&BY);
88 if(n==0){
89
90 printf("0\n");
91 continue;
92 }
93 AO%=mod;
94 BO%=mod;
95 AX%=mod;
96 AY%=mod;
97 BX%=mod;
98 BY%=mod;
99 ans.init(1);
100 init(cc);
101 pow(cc,n-1);
102
103 sab=(AO*BO)%mod;
104 LL res=(ans.mat[4][0]*sab)%mod+(ans.mat[4][1]*AO)%mod+(ans.mat[4][2]*BO)%mod+ans.mat[4][3]%mod+(AO*BO)%mod;
105 printf("%I64d\n",res%mod);
106 }
107 return 0;
108 }