## Editorial for Xoa day

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

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

#include <bits/stdc++.h>

using namespace std;
const int N = 50005;
const int D = 650;
const long long BASE = 1000000000000000000ll;
const int lg = 18;
struct BigNum {
int d; long long cs[D];
};

BigNum F[N], Fib[N];
int n, nn, t;

void SUM(BigNum a, BigNum b, BigNum& c) {
c.d = max(a.d, b.d);
//memset(c.cs, 0, sizeof(c.cs));
long long carry = 0, s;
for(int i=0; i<c.d; i++) {
s = a.cs[i] + b.cs[i] + carry;
carry = s / BASE;
c.cs[i] = s % BASE;
}
if (carry > 0) {
c.d++; c.cs[c.d - 1] = carry;
}
}

void SUM(BigNum a, BigNum b, BigNum c, BigNum& d) {
d.d = max(a.d, max(b.d, c.d));
//memset(c.cs, 0, sizeof(c.cs));
long long carry = 0, s;
for(int i=0; i<d.d; i++) {
s = a.cs[i] + b.cs[i] + c.cs[i] + carry;
carry = s / BASE;
d.cs[i] = s % BASE;
}
if (carry > 0) {
d.d++; d.cs[d.d - 1] = carry;
}
}

void WRITE(BigNum& a) {
string str;
for(int i=a.d-1; i >= 0; i--) {
ostringstream st;
st << a.cs[i]; str = st.str();
if (i < a.d - 1)
for(int j = lg - str.length(); j; j--) printf("0");
cout << str;
}
printf("\n");
}

void Init() {
Fib[1].d = 1; Fib[1].cs[0] = 1;
Fib[2] = Fib[1]; Fib[3] = Fib[1]; Fib[3].cs[0] = 2;
F[3].d = 1; F[3].cs[0] = 4;
nn = 3;
}

void DP(int n) {
for(int i=nn+1; i<=n; i++) {
SUM(Fib[i-1], Fib[i-2], Fib[i]);
SUM(Fib[i-1], Fib[i-3], F[i-1], F[i]);
}
nn = n;
}

int main()
{
Init();
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
if (nn < n) DP(n);
WRITE(F[n]);
}
return 0;
}


#### Code mẫu của hieult

import java.util.*;
import java.math.*;
import java.io.*;
class Matrix{
BigInteger [][]a;
Matrix(){
a = new BigInteger[2][2];
for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++) a[i][j] = BigInteger.ZERO;
}

Matrix mul(Matrix M){
Matrix res = new Matrix();

for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++) for(int k = 0; k < 2; k++){
}

return res;
}

Matrix mu(int k){
Matrix res = new Matrix();
Matrix sqr = new Matrix();

for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++){
res.a[i][j] = a[i][j];
sqr.a[i][j] = a[i][j];
}
k--;
while(k > 0){
if(k % 2 == 1) res = res.mul(sqr);
sqr = sqr.mul(sqr);
k >>= 1;
}

return res;
}

}
public class Main {

public static int test;
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
test = sc.nextInt();
for(int itest = 0; itest < test; itest++){
int n = sc.nextInt();
Matrix I = new Matrix();
for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++) {
I.a[i][j] = BigInteger.ZERO;
if(i + j > 0) I.a[i][j] = BigInteger.ONE;
}
Matrix A = I.mu((n - 1));
BigInteger res = BigInteger.ZERO;
for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++) {
if(i + j > 0) res = res.add(A.a[i][j]);
}
System.out.println(res);
}
//        System.out.println(System.currentTimeMillis() - time);
}

}