hdu 4686 Arc of Dream (构造矩阵，快速幂)
题意：
An Arc of Dream is a curve defined by following function:
where a 0 = A0 a i = a i-1_AX+AY b 0 = B0 b i = b i-1_BX+BY What is the value of AoD(N) modulo 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]的辅助项。**
对于这道题：
然后矩阵快速幂即可。
1A
/* ***********************************************
Author :111qqz
Created Time :2017年10月01日 星期日 13时34分52秒
File Name :4686.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define PB push_back
14#define fst first
15#define sec second
16#define lson l,m,rt<<1
17#define rson m+1,r,rt<<1|1
18#define ms(a,x) memset(a,x,sizeof(a))
19typedef long long LL;
20#define pi pair < int ,int >
21#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=10;
7const LL mod = 1E9+7;
8LL n,A0,Ax,Ay,B0,Bx,By;
9struct Mat
10{
11 LL mat[N][N];
12 void clear()
13 {
14 ms(mat,0);
15 }
16 void pr()
17 {
18 for ( int i = 0 ; i < 5 ; i++)
19 for ( int j = 0 ; j < 5 ; j++)
20 printf("%lld%c",mat[i][j],j==4?'\n':' ');
21 }
22}M,M1;
23Mat operator * (Mat a,Mat b)
24{
25 Mat c;
26 c.clear();
27 for ( int i = 0 ; i < 5 ; i++)
28 for ( int j = 0 ; j < 5 ; j++)
29 for ( int k = 0 ; k < 5 ; k++)
30 {
31 a.mat[i][k]%=mod;
32 b.mat[k][j]%=mod;
33 c.mat[i][j] = (c.mat[i][j] + a.mat[i][k] * b.mat[k][j] % mod) %mod;
34 }
35 return c;
36}
37Mat operator ^ (Mat a,LL b)
38{
39 Mat ret;
40 ret.clear();
41 for ( int i = 0 ; i < 5 ; i++) ret.mat[i][i] = 1;
42 while (b>0)
43 {
44 if (b&1)
45 ret = ret * a;
46 b = b>>1LL;
47 a = a * a;
48 }
49 return ret;
50}
51LL solve()
52{
53 M1.clear();
54 M.clear();
55 M.mat[0][0] = Ax*Bx;
56 M.mat[0][1] = Ax*By;
57 M.mat[0][2] = Ay*Bx;
58 M.mat[0][3] = Ay*By;
1 M.mat[1][1] = Ax;
2 M.mat[1][3] = Ay;
3 M.mat[2][2] = Bx;
4 M.mat[2][3] = By;
5 M.mat[3][3] = 1;
6 M.mat[4][0] = 1;
7 M.mat[4][4] = 1;
1 M1.mat[0][0] = A0*B0;
2 M1.mat[1][0] = A0;
3 M1.mat[2][0] = B0;
4 M1.mat[3][0] = 1;
5 M1.mat[4][0] = 0;
1 Mat ans;
2 ans.clear();
3 ans = (M ^ (n))*M1;
4 // ans.pr();
5 return ans.mat[4][0];
6}
7int main()
8{
9 #ifndef ONLINE_JUDGE
10 freopen("./in.txt","r",stdin);
11 #endif
12 while (~scanf("%lld%lld%lld%lld%lld%lld%lld",&n,&A0,&Ax,&Ay,&B0,&Bx,&By))
13 {
14 LL ans = solve();
15 ans = (ans % mod + mod )%mod;
16 printf("%lld\n",ans);
17 }
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}