A Short problem

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2461 Accepted Submission(s): 864

Problem Description

　　According to a research, VIM users tend to have shorter fingers, compared with Emacs users.
　　Hence they prefer problems short, too. Here is a short one:
　　Given n (1 <= n <= 10¹⁸), You should solve for
g(g(g(n))) mod 10⁹ + 7
　　where
g(n) = 3g(n - 1) + g(n - 2)
g(1) = 1
g(0) = 0

Input

　　There are several test cases. For each test case there is an integer n in a single line.
　　Please process until EOF (End Of File).

Output

　　For each test case, please print a single line with a integer, the corresponding answer to this case.

Sample Input

0
1
2

Sample Output

0
1
42837

三层复合函数。写完交上去TLE，不解。查了题解发现有循环节。循环节的话用set::find函数来查找是否存在过，若存在则输出循环节，不存在则插入当前数值继续循环。

然后就是矩阵快速幂了。递推式： $\begin{bmatrix} g_{n}&0 \\ g_{n-1}&0 \end{bmatrix} = \begin{bmatrix} 3&-1 \\ 1&0 \end{bmatrix}^{n-1} * \begin{bmatrix} g_{1}&0 \\ g_{0}&0 \end{bmatrix}$ （当某一层n为0的时候加上mod否则可能出错）

代码：

#include<iostream>

#include<algorithm>

#include<cstdlib>

#include<sstream>

#include<cstring>

#include<cstdio>

#include<string>

#include<deque>

#include<stack>

#include<cmath>

#include<queue>

#include<set>

#include<map>

using namespace std;

typedef long long LL;

#define INF 0x3f3f3f3f

const long long mod=1000000007;

struct mat

{

    LL pos[2][2];

    mat(){memset(pos,0,sizeof(pos));}

};

inline mat mul(const mat &a,const mat &b,const LL &mod)

{

    mat c;

    for (int i=0; i<2; i++)

    {

        for (int j=0; j<2; j++)

        {

            for (int k=0; k<2; k++)

            {

                c.pos[i][j]+=((a.pos[i][k])%mod*(b.pos[k][j])%mod)%(mod);

            }

        }

    }

    return c;

}

inline mat matpow(mat a,LL b,const LL &mod)

{

    mat r;

    r.pos[1][1]=r.pos[0][0]=1;

    mat bas=a;

    while (b!=0)

    {

        if(b&1)

            r=mul(r,bas,mod);

        bas=mul(bas,bas,mod);

        b>>=1;

    }

    return r;

}

int main(void)

{

    mat one,t;

    LL n,ans;

    one.pos[0][0]=1;

    one.pos[0][1]=0;

    t.pos[0][0]=3;

    t.pos[0][1]=t.pos[1][0]=1;

    mat poww,initt;

    while (cin>>n)

    {

        if(n==0)

        {

            cout<<"0"<<endl;

            continue;

        }

        poww=t,initt=one;

        poww=matpow(poww,n-1,183120);

        initt=mul(initt,poww,183120);

        ans=initt.pos[0][0];

        ans+=183120;

        poww=t,initt=one;

        poww=matpow(poww,ans-1,222222224);

        initt=mul(initt,poww,222222224);

        ans=initt.pos[0][0];

        ans+=222222224;

        poww=t,initt=one;

        poww=matpow(poww,ans-1,1000000007);

        initt=mul(initt,poww,1000000007);

        cout<<initt.pos[0][0]%1000000007<<endl;

    }

    return 0;

}

巴特西

HDU——4291A Short problem（矩阵快速幂+循环节）

A Short problem

最新文章

热门文章