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 flashmt

const fi='';
      fo='';
      k=111539786;
      max=1000;
var n,t,i,num:longint;
    a:array[1..max] of int64;
    q:array[1..10000] of longint;
    v:array[1..10000] of int64;
procedure init;
var i:longint;
begin
     fillchar(a,sizeof(a),0);
     a[1]:=1;
     a[2]:=1;
     for i:=3 to max do
         a[i]:=(a[i-1]+a[i-2]) mod k;
end;
function check(t,j:longint):boolean;
var kt:boolean; i:longint;
begin
     kt:=true;
     for i:=num downto j do
         if q[i]=t then
         begin
              kt:=false;
              break;
         end;
     check:=kt;
end;
function find(t,j:longint):longint;
var i:longint;
begin
     for i:=num downto j+1 do
         if q[i]=t then
         begin
              find:=i;
              break;
         end;
end;
procedure add(n:longint);
var i,j,t:longint; kt:boolean; x,y,z:longint;
begin
     num:=1; q[1]:=n; i:=1;
     repeat
           if q[i]<=max then
           begin
                inc(i);
                continue;
           end;
           if check(q[i] div 2,i+1) then
           begin
                inc(num);
                q[num]:=q[i] div 2;
           end;
           if check(q[i] div 2+1,i+1) then
           begin
                inc(num);
                q[num]:=q[i] div 2+1;
           end;
           if (q[i] mod 2 = 0) and check(q[i] div 2-1,i+1) then
           begin
                inc(num);
                q[num]:=q[i] div 2-1;
           end;
           inc(i);
     until i>num;
     fillchar(v,sizeof(v),0);
     for i:=num downto 1 do
     begin
               if q[i]<=max then v[i]:=a[q[i]]
               else
               begin
                    x:=find(q[i] div 2,i);
                    y:=find(q[i] div 2+1,i);
                    if q[i] mod 2=0 then
                       z:=find(q[i] div 2-1,i);
                    if q[i] mod 2=1 then
                       v[i]:=((v[x]*v[x]) mod k+(v[y]*v[y]) mod k) mod k
                    else v[i]:=((v[x]*v[y]) mod k+(v[x]*v[z]) mod k) mod k;
               end;
     end;
end;
begin
     assign(input,fi);
     reset(input);
     assign(output,fo);
     rewrite(output);
     init;
     readln(t);
     for i:=1 to t do
     begin
          readln(n);
          if n+1<=max then writeln(a[n+1])
          else
          begin
                add(n+1);
                writeln(v[1]);
          end;
     end;
     close(input);
     close(output);
end.

Code mẫu của happyboy99x

#include<cstdio>

#define MOD 111539786LL
typedef long long LL;

class FibonacciMatrix {
    public:
        LL a[2][2];

        FibonacciMatrix() {
            a[0][0] = a[0][1] = a[1][0] = 1LL;
            a[1][1] = 0LL;
        }

        FibonacciMatrix(LL p, LL q, LL r, LL s) {
            a[0][0] = p; a[0][1] = q;
            a[1][0] = r; a[1][1] = s;
        }

        inline FibonacciMatrix operator % (const LL & mod) {
            return FibonacciMatrix(a[0][0] % mod, a[0][1] % mod, a[1][0] % mod, a[1][1] % mod);
        }

        inline FibonacciMatrix operator * (const FibonacciMatrix & mat) {
            return FibonacciMatrix(a[0][0] * mat.a[0][0] + a[0][1] * mat.a[1][0],
                    a[0][0] * mat.a[0][1] + a[0][1] * mat.a[1][1],
                    a[1][0] * mat.a[0][0] + a[1][1] * mat.a[1][0], 
                    a[1][0] * mat.a[0][1] + a[1][1] * mat.a[1][1]) % MOD;
        }

        inline FibonacciMatrix operator ^ (const int & n) {
            if(n == 1) return FibonacciMatrix();
            FibonacciMatrix res = *this ^ (n >> 1);
            return n & 1 ? res * res * FibonacciMatrix() : res * res;
        }
};

int main() {
    int tc; scanf("%d", &tc);
    while(tc--) {
        int n; scanf("%d", &n);
        printf("%lld\n", (FibonacciMatrix() ^ n).a[0][0]);
    }
    return 0;
}

Code mẫu của ladpro98

program fibonaci;

const   base=111539786;
        maxN = 27879435;
var     i,t,n:longint;
        fiber:array[0..maxN] of longint;


function fib(n:longint):longint;
var     t,tt:int64;
begin
        if fiber[n]<>0 then exit(fiber[n]);


                        t:=fib(n div 2) mod base;
                        tt:=fib(n div 2-1) mod base;
        if n mod 2 = 0 then
                begin
                        fiber[n]:=(sqr(t) mod base + sqr(tt) mod base) mod base;
                        exit(fiber[n]);
                end
                else
                begin
                        fiber[n]:=(t*(tt mod base +fib(n div 2+1))) mod base;
                        exit(fiber[n]);
                end;
end;

begin
        fiber[0]:=1;
        fiber[1]:=1;
        readln(T);
        for i:=1 to t do
        begin
                readln(n);
                writeln(fib(n mod (maxn-3)));
        end;
end.

Code mẫu của RR

//Written by Nguyen Thanh Trung
{$IFDEF RR}
  {$R+,Q+}
  {$Mode objFPC}
  {$inline off}
{$ELSE}
  {$R-,Q-}
  {$inline on}
{$ENDIF}
uses math;
const
  FINP          =       {$IFDEF RR}'input.txt';  {$ELSE} ''; {$ENDIF}
  FOUT          =       {$IFDEF RR}'output.txt'; {$ELSE} ''; {$ENDIF}
  base          =       111539786;
type
  matrix        =       array[0..1,0..1] of longint;
const
  a             :       matrix=((0,1),(1,1));
var
  f1,f2         :       text;
  n,test        :       longint;
  x             :       matrix;

procedure openF;
    begin
      assign(f1,FINP); reset(f1);
      assign(f2,FOUT); rewrite(f2);
    end;
procedure closeF;
    begin
      close(f1);
      close(f2);
    end;
operator * (a,b:matrix) c:matrix;
    var
      i,j,k:longint;
    begin
      fillchar(c,sizeof(c),0);
      for i:=0 to 1 do
      for j:=0 to 1 do
        for k:=0 to 1 do
          c[i,j]:=(c[i,j]+int64(a[i,k])*(b[k,j])) mod base;
    end;
function cal(n:longint):matrix; inline;
    var
      temp:matrix;
    begin
      if n=1 then exit(a);
      temp:=cal(n>>1);
      temp:=temp*temp;
      if n and 1=1 then
        temp:=temp*a;
      exit(temp);
    end;

begin
  openF;
  read(f1,test);
  for test:=1 to test do
    begin
      read(f1,n);
      x:=cal(n);
      writeln(f2,x[1,1]);
    end;
  closeF;
end.

Code mẫu của hieult

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
//include<conio.h>
#define ep 0.000000001
#define maxn 10011
#define oo 1000000000
#define ooo 1ll << 62
#define mod 111539786
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define fi first 
#define se second
#define max_size 2
double const PI=4*atan(1);

typedef long long int64;

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

struct Matrix{
    int64 x[max_size][max_size];
    Matrix(){};
    Matrix(int64 a[2][2]) { for(int i = 0; i < max_size; i++) for(int j = 0; j < max_size; j++) x[i][j] = a[i][j];}
    friend Matrix operator * (const Matrix &a, const Matrix &b){
        Matrix c;
        for(int i = 0; i < max_size; i++) for(int j = 0; j < max_size; j++){
            c.x[i][j] = 0;
            for(int k = 0; k < max_size; k++) c.x[i][j] = (c.x[i][j] + a.x[i][k] * b.x[k][j]) % mod;
        } 
        return c;
    }
    friend Matrix operator ^ (const Matrix &a, const int &k){
        if(k == 1) return a;
        Matrix c = a ^ (k / 2);
        if(k & 1) return c * c * a;
        else return c * c;
    }
};

int test, n;

int main(){
    //freopen("input.in","r",stdin); 
   // freopen("output.out","w",stdout);
    int64 u[2][2] = {1, 1, 1, 0};
    Matrix I = Matrix(u);
    scanf("%d",&test);
    while(test--){
        scanf("%d",&n);
        if(n == 1) printf("1\n");
        else{
            Matrix A = I ^ (n - 1);
            printf("%lld\n",(A.x[0][0] + A.x[1][0]) % mod);
        }
    }
    return 0;
     // getch();
}

Code mẫu của ll931110

{$MODE DELPHI}
program LATGACH4;
type
  mat = array[1..2,1..2] of int64;
const
  input  = '';
  output = '';
  rem = 111539786;
  st: mat = ((0,1),(1,1));
var
  nTest,i,n: integer;
  fi,fo: text;

procedure openfile;
begin
  assign(fi, input);
    reset(fi);

  assign(fo, output);
    rewrite(fo);
end;

function mul(a,b: mat): mat;
var
  c: mat;
  i,j,k: integer;
begin
  for i := 1 to 2 do
    for j := 1 to 2 do
      begin
        c[i,j] := 0;
        for k := 1 to 2 do c[i,j] := (c[i,j] + a[i,k] * b[k,j]) mod rem;
      end;
  mul := c;
end;

function calc(x: mat; p: integer): mat;
var
  tmp: mat;
begin
  if p = 1 then exit(x);
  tmp := calc(x,p div 2);

  tmp := mul(tmp,tmp);
  if odd(p) then tmp := mul(tmp,x);
  calc := tmp;
end;

procedure solve;
var
  res: mat;
begin
  readln(fi, n);
  res := calc(st,n + 1);
  writeln(fo, res[1,2]);
end;

procedure closefile;
begin
  close(fo);
  close(fi);
end;

begin
  openfile;

  readln(fi, nTest);
  for i := 1 to nTest do solve;

  closefile;
end.

Code mẫu của skyvn97

#include<stdio.h>
#define MAX   200000
#define MOD   111539786
typedef unsigned long long ull;
ull n;
ull fib[MAX+2];
int t,ct;
void init(void)
{
     ull i;
     fib[1]=1;
     fib[2]=1;
     for (i=3;i<MAX;i=i+1) fib[i]=(fib[i-1]+fib[i-2])%MOD;
}
ull fibo(ull n)
{
    if (n<MAX) return (fib[n]);
    if (n%2==1)
       {
        ull k=(n+1)/2;
        ull f1=fibo(k);
        ull f2=fibo(k-1);
        return ((f1*f1+f2*f2)%MOD);
       }
    if (n%2==0)
       {
        ull k=n/2;
        ull f1=fibo(k);
        ull f2=fibo(k-1);
        return ((f1*f1+2*f1*f2)%MOD);
       }
}
int main(void)
{
    init();
    scanf("%d",&t);
    for (ct=1;ct<=t;ct=ct+1)
        {
         scanf("%llu",&n);
         printf("%llu\n",fibo(n+1));
        }
}

Code mẫu của khuc_tuan

//{$APPTYPE CONSOLE}
 {$MODE DELPHI}

const
    SD = 111539786;

type
    TArr1 = array[1..2,1..2] of int64;

var
    st, t, n : integer;
    a : TArr1;

function mul( a, b : TArr1) : TArr1;
var
    c : TArr1;
begin
    c[1,1] := (a[1,1] * b[1,1] + a[1,2] * b[2,1]) mod SD;
    c[1,2] := (a[1,1] * b[1,2] + a[1,2] * b[2,2]) mod SD;
    c[2,1] := (a[2,1] * b[1,1] + a[2,2] * b[2,1]) mod SD;
    c[2,2] := (a[2,1] * b[1,2] + a[2,2] * b[2,2]) mod SD;
    mul := c;
end;

function get( a : TArr1; n : integer) : TArr1;
var
    r : TArr1;
begin
    if n=1 then get := a
    else
    begin
        r := get( a, n div 2);
        if n mod 2 = 0 then get := mul( r, r)
        else get := mul( r, mul( r, a));
    end;
end;

begin
    read(st);
    for t:=1 to st do
    begin
        read(n);
        a[1,1] := 0;
        a[1,2] := 1;
        a[2,2] := 1;
        a[2,1] := 1;
        if (n=0) or (n=1) then writeln(1)
        else
        begin
            a := get( a, n - 1);
            writeln( (a[1,2] + a[2,2]) mod SD);
        end;
    end;
end.