Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của ladpro98

Copy

#include <bits/stdc++.h>
const long long MOD = 1000000000000007ll;
using namespace std;

struct mat {
    long long a[4][4];
} a, b;
int t, n;
long long F[5], T[5];

long long mul(long long a, long long b) {
    long long c = 0;
    while (b) {
        if (b & 1) {
            c += a;
            if (c >= MOD) c -= MOD;
        }
        a += a; if (a >= MOD) a -= MOD;
        b /= 2;
    }
    return c;
}

mat operator * (mat a, mat b) {
    mat c;
    for(int i = 0; i < 4; i++)
        for(int j = 0; j < 4; j++) {
            c.a[i][j] = 0;
            for(int k = 0; k < 4; k++)
                c.a[i][j] = (c.a[i][j] + mul(a.a[i][k], b.a[k][j])) % MOD;
        }
    return c;
}

mat POW(int p) {
    if (p == 1) return a;
    mat x = POW(p / 2);
    x = x * x;
    if (p & 1) x = x * a;
    return x;
}

int main() {
    scanf("%d", &t);
    a.a[0][0] = a.a[0][1] = a.a[1][1] = a.a[1][2] = a.a[1][3] = a.a[2][1] = a.a[3][2] = 1;
    F[1] = 1; F[2] = 3; F[3] = 6; T[1] = 1; T[2] = 2; T[3] = 3;
    while (t--) {
        scanf("%d", &n);
        if (n <= 3) printf("%lld\n", F[n]);
        else {
            b = POW(n - 2);
            printf("%lld\n", (F[2] * b.a[0][0] + T[3] * b.a[0][1] + T[2] * b.a[0][2] + T[1] * b.a[0][3]) % MOD);
        }
    }
    return 0;
}

Code mẫu của skyvn97

Copy

#include<cassert>
#include<cstdio>
#include<iostream>
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
using namespace std;
typedef long long ll;
const ll mod=(ll)   1e15+7LL;
struct Number {
    ll val;
    Number() {
        val=0;
    }
    Number(ll x) {
        val=x%mod;
    }
    Number operator + (const Number &x) const {
        return (Number(val+x.val));
    }
    Number operator * (const Number &x) const {
        ll res=0;
        ll add=val;
        ll k=x.val;
        while (k>0) {
            if (k&1) res=(res+add)%mod;
            add=(add<<1)%mod;
            k>>=1;
        }
        return (Number(res));
    }
};
ostream& operator << (ostream &str,const Number &x) {
    return (str<<x.val);
}
struct Matrix {
    int m,n;
    Number d[7][7];
    Matrix() {
        m=n=0;
    }
    Matrix(int _m,int _n) {
        m=_m;
        n=_n;
        REP(i,m) REP(j,n) d[i][j]=Number(0);
    }
    Matrix operator * (const Matrix &a) const {
        int x=m;
        int y=n;
        int z=a.n;
        Matrix res=Matrix(x,z);
        REP(i,x) REP(j,y) REP(k,z) res.d[i][k]=res.d[i][k]+d[i][j]*a.d[j][k];
        return (res);
    }
    Matrix operator ^ (ll k) const {
        Matrix res=Matrix(n,n);
        REP(i,n) REP(j,n) res.d[i][j]=Number(i==j);
        Matrix mul=*this;
        while (k>0) {
            if (k&1) res=res*mul;
            mul=mul*mul;
            k>>=1;
        }
        return (res);
    }
};
const int Mul[][4]={{0,0,1,1},{1,0,1,1},{0,1,1,1},{0,0,0,1}};
const int Fst[]={1,2,3,6};
Number answer(ll x) {
    if (x<=3) return (Number(x*(x+1)/2));
    Matrix fst=Matrix(1,4);
    Matrix mul=Matrix(4,4);
    REP(i,4) fst.d[0][i]=Number(Fst[i]);
    REP(i,4) REP(j,4) mul.d[i][j]=Number(Mul[i][j]);
    return ((fst*(mul^(x-3))).d[0][3]);
}
void check(void) {
    ll x[40];
    ll sum=0;
    FOR(i,1,3) x[i]=i;
    FOR(i,1,10000) {
        if (i>3) x[i%4]=(x[(i-1)%4]+x[(i-2)%4]+x[(i-3)%4])%mod;
        sum=(sum+x[i%4])%mod;
        assert(sum==answer(i).val);
    }
}
inline ll nextlong(void) {
    ll x;
    cin>>x;
    return (x);
}
int main(void) {
#ifndef ONLINE_JUDGE
    check();
    cerr<<"OK"<<endl;
#endif
    ios::sync_with_stdio(false);
    REP(zz,nextlong()) cout<<answer(nextlong())<<"\n";
    return 0;
}