分解

题目链接：http://www.51nod.com/contest/problem.html#!problemId=1537

矩阵快速幂

找规律可知，一定存在m，满足(1+sqrt(2)) ^n=sqrt(m) +sqrt(m-1)，但是该如何找到这个m呢？注意到n的范围是1e18，所以只能是O（1）或者O（lgn）的做法。

(1+sqrt(2)) ^n的展开式中只包含整数项和sqrt(2)项，设(1+sqrt(2)) ^n=a+b*sqrt(2)，a和b均为正整数。

初始状态当n=1时，a=1，b=1；然后构造出变换矩阵即可。

代码如下：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #define M (long long)(1e9+7)
 5 using namespace std;
 6 typedef long long LL;
 7 struct math{
 8     LL mp[2][2];
 9 }E,A;
10 /*
11 变换矩阵:
12 1 2
13 1 1
14 */
15 math mul_math(math a,math b){
16     math temp;
17     for(int i=0;i<2;++i)
18     for(int j=0;j<2;++j){
19         temp.mp[i][j]=0;
20         for(int k=0;k<2;++k)
21             temp.mp[i][j]+=(a.mp[i][k]*b.mp[k][j])%M;
22     }
23     return temp;
24 }
25 math pow_math(LL x){
26     math base=A,temp=E;
27     while(x){
28         if(x&1)temp=mul_math(temp,base);
29         base=mul_math(base,base);
30         x>>=1;
31     }
32     return temp;
33 }
34 int main(void){
35     for(int i=0;i<2;++i){
36         E.mp[i][i]=1;
37         A.mp[i][i]=1;
38     }
39     A.mp[1][0]=1;
40     A.mp[0][1]=2;
41     LL n;
42     cin>>n;
43     math temp=pow_math(n-1);
44     LL a=(temp.mp[0][0]+temp.mp[0][1])%M;
45     a=(a*a)%M;
46     LL b=(temp.mp[1][0]+temp.mp[1][1])%M;
47     b=(b*b)%M;
48     b=(b+b)%M;
49     cout<<max(a,b)<<endl;
50 }