Untitled

 avatar
unknown
plain_text
2 months ago
1.2 kB
3
Indexable
// ThonqRiu
#include <bits/stdc++.h>
#define endl '\n'
#define maxn 105
#define MOD 1000000007
#define Task "bai1"
#define ll long long
using namespace std;
int t;
struct matrix{
    int val[maxn][maxn];
    matrix (){
        memset(val,0, sizeof(val));
    }

};
matrix Nhan(matrix A, matrix B){
    matrix res;
    for(int i = 1; i<=2; i++)
        for(int j = 1; j<=2; j++){

            for(int k = 1; k<=2; k++)
                res.val[i][j] = (res.val[i][j] + 1ll*A.val[i][k]*B.val[k][j]) % MOD;
        }
    return res;
}
matrix Mu(matrix A, ll x){
    matrix C;
    for(int i = 1; i<=2; i++) C.val[i][i] = 1;
    if(x == 0) return C;
    matrix B = Mu(A,x / 2);
    B = Nhan(B,B);
    if(x % 2 == 1) B = Nhan(B,A);
    return  B;
}
int main()
{
    ios_base:: sync_with_stdio(0);
    cin.tie(nullptr);
    if(fopen(Task".inp","r")){
        freopen(Task".inp","r",stdin);
    }
    cin >> t;
    while(t--){
        ll x; cin >> x;
        matrix T;
        T.val[1][1] = T.val[2][1] = 1;
        T.val[1][2] = 2;
        matrix B = Mu(T,x - 1);
        cout << (B.val[1][1] + B.val[1][2])  % MOD << endl;
    }
}
Editor is loading...
Leave a Comment