Untitled
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