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

#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++){
            res.a[i][j] = (res.a[i][j].add(a[i][k].multiply(M.a[k][j])));
        }

        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);
    }


}