1039 愉快的递推式 矩阵乘法

链接：https://ac.nowcoder.com/acm/contest/26656/1039
来源：牛客网

题目描述

已知 f(1)=1,f(2)=1f(1)=1,f(2)=1f(1)=1,f(2)=1。
对于 n>2n>2n>2 的任意 f(n)f(n)f(n), 都满足 f(n)=3f(n−1)+2f(n−2)+2f(n)=3f(n-1)+2f(n-2)+2f(n)=3f(n−1)+2f(n−2)+2, 求 f(n)f(n)f(n)。

输入描述:

一个n (1≤n≤1012)(1 /le n /le 10^{12})(1≤n≤1012)。

输出描述:

输出一行表示f(n)，答案对1000000007 取模。

示例1

输入

复制 3

3

输出

复制 7

7

示例2

输入

复制 4

4

输出

复制 25

25

示例3

输入

复制 1000000000000

1000000000000

输出

复制 33033517

33033517

备注:

2022.1.12更新了数据，by@王清楚

分析

自己写还是失败了，不知道错在哪里。

//-------------------------代码----------------------------

#define int ll
const ll mod = 1e9 + 7;

struct Node {
    ll a[3][3] = {
        {3,2,1},
        {1,0,0},
        {0,0,1}
    };
    Node operator* (Node b) {
        Node x;
        ms(x.a,0);
        for(int i = 0;i<3;i++) {
            for(int j = 0;j<3;j++) {
                for(int k = 0;k<3;k++) {
                    x.a[i][j] = x.a[i][j] % mod + this->a[i][k] * b.a[k][j] % mod;
                    x.a[i][j] %= mod;
                }
            }
        }
        return x;
    }
};

Node quick(Node a,ll ans) {
    if(ans == 1) {
        return a;
    }
    Node x;
    ans -- ;
    while( ans ) {
        if( ans & 1 ) {
            x = x * a;
        }
        a = a * a ;
        ans >>= 1;
    }
    return x;
}

void solve(ll n)
{
    if(n == 1 || n == 2) {
        cout<<1<<endl;
        return;
    }
    Node a;
    a = quick(a, n - 1);

    Node f;
    ms(f.a,0);
    f.a[0][0] = 1;
    f.a[1][0] = 1;
    f.a[2][0] = 2;
    f = a * f ;
    ll fin = (f.a[1][0]) % mod;
//     dbb(f.a[0][0],f.a[1][0]);
    cout<<fin<<endl;
}

signed main(){
    clapping();TLE;

    ll n;
//    int t;cin>>t;while(t -- )
//     while(cin>>n)
//     while(cin>>n)
        cin>>n;
        solve(n);
//    {solve(); }
    return 0;
}

/*样例区


*/

//------------------------------------------------------------