即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

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

编程语言 algzjh 11℃ 0评论
本文目录
[隐藏]

1.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+m1


解题思路:先写出前几项


(1+2)1=2+1=12+1+12


(1+2)2=9+8=32+321


(1+2)3=50+49=72+1+72


(1+2)4=289+288=172+1721


(1+2)5=1682+1681=412+1+412





设数列:


a1=1,a2=3,a3=7,a4=17,a5=41,


an=2an1+an2


所以当n<0时,输出”No”;


当n>0时:


若n为奇数,m=(an)2+1


若n为偶数,m=(an)2


[anan1]=[2110][an1an2]=[2110]n2[a2a1]


用矩阵快速幂加速


考察内容:数学,快速幂


复杂度: O(logn)


题目难度: ★★★★

#include
#include
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"<else if(n==0) cout<<"1"<else if(n==1) cout<<"2"<else if(n==2) cout<<"9"<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<else cout<<(an*an)%MOD<return 0;
}

转载请注明:CodingBlog » 中南大学第十一届大学生程序设计竞赛-COJ1895-Apache is late again

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情