题意：#
An Arc of Dream is a curve defined by the following function:
$$ \text{AoD}(N) = \sum_{i=0}^{N-1} a_i b_i $$where:
$$ a_0 = A_0, \quad a_i = a_{i-1} A_X + A_Y $$$$ b_0 = B_0, \quad b_i = b_{i-1} B_X + B_Y $$What is the value of \( \text{AoD}(N) \pmod{1{,}000{,}000{,}007} \)?
思路：#
看n的1E18的范围也知道是矩阵快速幂。。
难点还是构造矩阵。
构造矩阵主要凭借经验，但是还是有一些规律可循：
1. 对于求和的式子，如 s[n] = sum{F[1]..F[n]}类似的式子，我们只需要考虑如何构造F[n]即可。
2. 尽量将要构造的表达式展开成，第n项，与前面项(第n-1项等)有关的形式。
3. 观察2中展开的表达式的系数，每一个系数都要出现在转移矩阵M中。
4. 观察2中展开的表达式的项，基本每一项都要整体或者以其他形式出现在初始矩阵M1中
5. 我们并不很关心初始项。
6. 难点其实在于构造M1矩阵，也就是说哪些项是重要的。一般而言，**可能有的项是，s[n],f[n]，常数项，以及为了构造出f[n]的辅助项。**
对于这道题，展开第 \( n \) 项递推式：
$$ a_n b_n = (a_{n-1} A_X + A_Y)(b_{n-1} B_X + B_Y) = A_X B_X (a_{n-1} b_{n-1}) + A_X B_Y a_{n-1} + A_Y B_X b_{n-1} + A_Y B_Y $$$$ a_n = A_X a_{n-1} + A_Y $$$$ b_n = B_X b_{n-1} + B_Y $$$$ S_n = S_{n-1} + a_{n-1} b_{n-1} $$构造状态转移矩阵方程：
$$ \begin{bmatrix} a_n b_n \\ a_n \\ b_n \\ 1 \\ S_n \end{bmatrix} = \begin{bmatrix} A_X B_X & A_X B_Y & A_Y B_X & A_Y B_Y & 0 \\ 0 & A_X & 0 & A_Y & 0 \\ 0 & 0 & B_X & B_Y & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} a_{n-1} b_{n-1} \\ a_{n-1} \\ b_{n-1} \\ 1 \\ S_{n-1} \end{bmatrix} $$然后矩阵快速幂计算 \( M^N \times M_1 \) 即可。
1A
代码实现
1/* ***********************************************
2Author :111qqz
3Created Time :2017年10月01日 星期日 13时34分52秒
4File Name :4686.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define PB push_back
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28
29using namespace std;
30const double eps = 1E-8;
31const int dx4[4]={1,0,0,-1};
32const int dy4[4]={0,-1,1,0};
33const int inf = 0x3f3f3f3f;
34const int N=10;
35const LL mod = 1E9+7;
36LL n,A0,Ax,Ay,B0,Bx,By;
37struct Mat
38{
39 LL mat[N][N];
40 void clear()
41 {
42 ms(mat,0);
43 }
44 void pr()
45 {
46 for ( int i = 0 ; i < 5 ; i++)
47 for ( int j = 0 ; j < 5 ; j++)
48 printf("%lld%c",mat[i][j],j==4?'\n':' ');
49 }
50}M,M1;
51Mat operator * (Mat a,Mat b)
52{
53 Mat c;
54 c.clear();
55 for ( int i = 0 ; i < 5 ; i++)
56 for ( int j = 0 ; j < 5 ; j++)
57 for ( int k = 0 ; k < 5 ; k++)
58 {
59 a.mat[i][k]%=mod;
60 b.mat[k][j]%=mod;
61 c.mat[i][j] = (c.mat[i][j] + a.mat[i][k] * b.mat[k][j] % mod) %mod;
62 }
63 return c;
64}
65Mat operator ^ (Mat a,LL b)
66{
67 Mat ret;
68 ret.clear();
69 for ( int i = 0 ; i < 5 ; i++) ret.mat[i][i] = 1;
70 while (b>0)
71 {
72 if (b&1)
73 ret = ret * a;
74 b = b>>1LL;
75 a = a * a;
76 }
77 return ret;
78}
79LL solve()
80{
81 M1.clear();
82 M.clear();
83 M.mat[0][0] = Ax*Bx;
84 M.mat[0][1] = Ax*By;
85 M.mat[0][2] = Ay*Bx;
86 M.mat[0][3] = Ay*By;
87
88 M.mat[1][1] = Ax;
89 M.mat[1][3] = Ay;
90 M.mat[2][2] = Bx;
91 M.mat[2][3] = By;
92 M.mat[3][3] = 1;
93 M.mat[4][0] = 1;
94 M.mat[4][4] = 1;
95
96 M1.mat[0][0] = A0*B0;
97 M1.mat[1][0] = A0;
98 M1.mat[2][0] = B0;
99 M1.mat[3][0] = 1;
100 M1.mat[4][0] = 0;
101
102 Mat ans;
103 ans.clear();
104 ans = (M ^ (n))*M1;
105 // ans.pr();
106 return ans.mat[4][0];
107}
108int main()
109{
110 #ifndef ONLINE_JUDGE
111 freopen("./in.txt","r",stdin);
112 #endif
113 while (~scanf("%lld%lld%lld%lld%lld%lld%lld",&n,&A0,&Ax,&Ay,&B0,&Bx,&By))
114 {
115 LL ans = solve();
116 ans = (ans % mod + mod )%mod;
117 printf("%lld\n",ans);
118 }
119
120 #ifndef ONLINE_JUDGE
121 fclose(stdin);
122 #endif
123 return 0;
124}