中南大学第十一届大学生程序设计竞赛-COJ1895-Apache is late again

1895: Apache is late again

Submit Page Summary Time Limit: 1 Sec Memory Limit: 128 Mb Submitted: 7 Solved: 3
Description
Apache is a student of CSU. There is a math class every Sunday morning, but he is a very hard man who learns late every night. Unfortunate, he was late for maths on Monday. Last week the math teacher gave a question to let him answer as a punishment, but he was easily resolved. So the math teacher prepared a problem for him to solve. Although Apache is very smart, but also was stumped. So he wants to ask you to solve the problem. Questions are as follows: You can find a m made (1 + sqrt (2)) ^ n can be decomposed into sqrt (m) + sqrt (m-1), if you can output m% 100,000,007 otherwise output No.

Input
There are multiply cases. Each case is a line of n. (|n| <= 10 ^ 18)

Output
Line, if there is no such m output No, otherwise output m% 100,000,007.

Sample Input
2
Sample Output
9
Hint
Source
中南大学第十一届大学生程序设计竞赛

题目大意：给你一个n，让你计算能否找到一个m使得
(1+2√)n=m−−√+m−1−−−−−√
解题思路：先写出前几项
(1+2√)1=2√+1√=12+1−−−−−√+12−−√
(1+2√)2=9√+8√=32−−√+32−1−−−−−√
(1+2√)3=50−−√+49−−√=72+1−−−−−√+72−−√
(1+2√)4=289−−−√+288−−−√=172−−−√+172−1−−−−−−√
(1+2√)5=1682−−−−√+1681−−−−√=412+1−−−−−−√+412−−−√
…
设数列：
a1=1,a2=3,a3=7,a4=17,a5=41,⋯
an=2∗an−1+an−2
所以当n<0时，输出”No”；
当n>0时：
若n为奇数， m=(an)2+1
若n为偶数， m=(an)2
[anan−1]=[2110][an−1an−2]=[2110]n−2[a2a1]
用矩阵快速幂加速
考察内容：数学，快速幂
复杂度： O(logn)
题目难度： ★★★★

#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int MOD=1e8+7;

struct matrix
{
    LL v[2][2];
    matrix(){memset(v,0,sizeof(v));}
    matrix operator * (const matrix &m)
    {
        matrix c;
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
for(int k=0;k<2;k++)
                    c.v[i][j]+=(v[i][k]*m.v[k][j])%MOD;
return c;
    }
};

matrix M,E,ans;//E为单位矩阵,ans为M^(n-2)

void Init()//初始化
{
for(int i=0;i<2;i++)
        E.v[i][i]=1;
    M.v[0][0]=2;M.v[0][1]=1;
    M.v[1][0]=1;M.v[1][1]=0;
}

matrix pow(matrix p,LL k)
{
    matrix tmp=E;
while(k)
    {
if(k&1)
        {
            tmp=tmp*p;
            k--;
        }
        k>>=1;
        p=p*p;
    }
return tmp;
}

int main()
{
    ios::sync_with_stdio(false);
    LL n;
    Init();
while(cin>>n)
    {
if(n<0) cout<<"No"<<endl;
else if(n==0) cout<<"1"<<endl;
else if(n==1) cout<<"2"<<endl;
else if(n==2) cout<<"9"<<endl;
else
        {
            ans=pow(M,n-2);
            LL an=(ans.v[0][0]*3+ans.v[0][1]*1)%MOD;
if(n&1) cout<<((an*an)%MOD+1)%MOD<<endl;
else cout<<(an*an)%MOD<<endl;
        }
    }
return 0;
}