题解 | 牛牛学数列6

// #pragma GCC optimize(2)
#include <ext/rope>
#include <bits/stdc++.h>
using namespace __gnu_cxx;
using namespace std;

#define ll long long
#define f(x) for (ll i = 1; i <= x; i++)
#define f1(x) for (ll j = 1; j <= x; j++)
#define lowbit(x) ((-x) & x)
#define PII pair<ll, ll>
#define yes cout << "YES\n";
#define no cout << "NO\n";
#define bug cerr << "bug\n";
constexpr double eps = 1e-9;
constexpr ll Minn = 9223372036854775807;
constexpr ll Maxx = -9223372036854775807;

const ll mod = 1e9 + 7;
struct matrix
{
    ll c[4][4];
    matrix()
    {
        memset(c, 0, sizeof c);
    }
} A;

matrix operator*(matrix &a, matrix &b)
{
    matrix t;
    for (ll i = 1; i <= 3; i++)
    {
        for (ll j = 1; j <= 3; j++)
        {
            for (ll k = 1; k <= 3; k++)
            {
                t.c[i][j] = a.c[i][k] * b.c[k][j] + t.c[i][j];
                t.c[i][j] %= mod;
            }
        }
    }
    return t;
}

matrix ksm(matrix x, ll k)
{
    matrix res;
    f(3) res.c[i][i] = 1;
    while (k)
    {
        if (k & 1)
        {
            res = res * x;
        }
        x = x * x;
        k >>= 1;
    }
    return res;
}

void solve()
{
    ll n;
    cin >> n;
    if(n == 1){
        cout << 0;
    }
    else if(n == 2 || n == 3){
        cout << 1 ;
    }
    else {
        A.c[1][1] = A.c[2][1] = A.c[3][2] = A.c[1][3] = 1;
        A.c[1][2] = 2;
        matrix ans = ksm(A, n - 3);

        cout << ans.c[1][1] + ans.c[1][2] % mod << endl;
    }
}

int main()
{
    ios ::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
//    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}
/*   /\_/\
 *   (= ._.)
 *   / >  \>
 */