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='';
      maxn=10000;
      base=1000000000;
      dg=9;
type bignum=array[0..340] of longint;
var n,k:longint;
    re,p:bignum;
    g:array[0..maxn] of bignum;

procedure rf;
begin
     read(n,k);
end;

procedure plus(var a,b:bignum);
var i,mem,max:Longint;
begin
     if b[0]>a[0] then max:=b[0] else max:=a[0];
     mem:=0;
     for i:=1 to max do
     begin
          a[i]:=a[i]+b[i]+mem;
          if a[i]<base then mem:=0
          else
          begin
               mem:=1;
               a[i]:=a[i]-base;
          end;
     end;
     if mem>0 then
     begin
          inc(max);
          a[max]:=1;
     end;
     a[0]:=max;
end;

procedure minus(var a,b,c:bignum);
var i,mem:longint;
begin
     mem:=0;
     for i:=1 to b[0] do
     begin
          a[i]:=b[i]-c[i]-mem;
          if a[i]>0 then mem:=0
          else
          begin
               a[i]:=a[i]+base;
               mem:=1;
          end;
     end;
     a[0]:=b[0];
     while (a[0]>1) and (a[a[0]]=0) do dec(a[0]);
end;

procedure mul(var a:bignum);
var i,mem:longint;
begin
     mem:=0;
     for i:=1 to a[0] do
     begin
          a[i]:=a[i] shl 1+mem;
          if a[i]<base then mem:=0
          else
          begin
                mem:=1;
                a[i]:=a[i]-base;
          end;
     end;
     if mem>0 then
     begin
          inc(a[0]);
          a[a[0]]:=1;
     end;
end;

procedure pr;
var i,j:longint;
begin
     p[0]:=1; p[1]:=1;
     g[0,0]:=1; g[0,1]:=1; re[0]:=1;
     for i:=1 to k-1 do
     begin
          mul(p);
          for j:=0 to p[0] do g[i,j]:=p[j];
     end;
     for i:=k to n do
     begin
          mul(p);
          mul(re);
          if i>k then plus(re,g[i-k-1])
          else re[1]:=1;
          if i<=n-k-1 then minus(g[i],p,re);
     end;
end;

procedure wf;
var i,j,l:longint; s:string;
begin
     for i:=re[0] downto 1 do
     begin
          if i<re[0] then
          begin
               str(re[i],s);
               l:=length(s);
               for j:=l+1 to dg do write(0);
          end;
          write(re[i]);
     end;
end;

begin
     assign(input,fi); reset(input);
     assign(output,fo); rewrite(output);
     rf;
     pr;
     wf;
     close(input); close(output);
end.

Code mẫu của ladpro98

#include <bits/stdc++.h>
const int MOD = 100000000;
using namespace std;
typedef vector<int> big;

int n, k;
big F[10005];

big operator + (const big &a, const big &b) {
    big c; int carry = 0;
    for(int i = 0; i < a.size() || i < b.size(); i++) {
        if (i < a.size()) carry += a[i];
        if (i < b.size()) carry += b[i];
        c.push_back(carry % MOD);
        carry /= MOD;
    }
    if (carry) c.push_back(carry);
    return c;
}

big operator - (const big &a, const big &b) {
    big c; int borrow = 0, s;
    for(int i = 0; i < a.size(); i++) {
        s = a[i] - borrow;
        if (i < b.size()) s -= b[i];
        if (s < 0) {
            s += MOD;
            borrow = 1;
        }
        else 
            borrow = 0;
        c.push_back(s);
    }
    while (!c.empty() && c[c.size() - 1] == 0) c.pop_back();
    return c;

}

void print(big a) {
    printf("%d", a[a.size() - 1]);
    for(int i = a.size() - 2; i >= 0; i--)
        printf("%08d", a[i]);
    printf("\n");
}

int main() {
    scanf("%d %d", &n, &k);
    F[0].push_back(1);
    big prev; prev.push_back(1);
    big POW; POW.push_back(1);
    for(int i = 1; i <= n + 1; i++) {
        F[i] = prev;
        prev = prev + F[i];
        if (i >= k)
            prev = prev - F[i - k];
        if (i <= n)
            POW = POW + POW;
    }
    print(POW - F[n + 1]);
    return 0;
}

Code mẫu của RR

{$R+,Q+}
{$Mode objFPC}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=10000;
  oo=100000000;
type
  big=array[0..400] of longint;
var
  f1,f2:text;
  n,k:longint;
  d:array[-1..MAXN] of big;
  lt2:big;
procedure openF;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
  close(f1); close(f2);
end;
procedure solve;
var
  scs,nho,i,t:longint;
  temp:int64;
begin
  d[k][0]:=1; d[k][1]:=1;
  lt2[0]:=1; lt2[1]:=1;
  for i:=k+1 to n do
    begin
      scs:=max(max(d[i-1,0],d[i-k-1,0]),lt2[0]);
      nho:=0; t:=i-k-1;
      for scs:=1 to scs do
        begin
          temp:=d[i-1,scs]<<1-d[t,scs];
          temp+=int64(lt2[scs])+nho;
          if (temp<oo) and (temp>=0) then begin nho:=0; d[i,scs]:=temp; end
          else if temp>=0 then begin nho:=temp div oo; d[i,scs]:=temp mod oo; end
          else begin nho:=-1; d[i,scs]:=temp+oo; end;
        end;
      if nho>0 then
        begin inc(scs); d[i,scs]:=nho; end;
      d[i,0]:=scs;
      scs:=lt2[0]; nho:=0;
      for scs:=1 to scs do
        begin
          lt2[scs]:=lt2[scs]<<1+nho;
          if lt2[scs]<oo then nho:=0 else begin lt2[scs]-=oo; nho:=1; end;
        end;
      if nho>0 then begin inc(lt2[0]); lt2[lt2[0]]:=nho; end;
    end;
end;
procedure ans;
var
  i,ii:longint;
  s:string[10];
begin
  write(f2,d[n,d[n,0]]);
  for i:=d[n,0]-1 downto 1 do
    begin
      str(d[n,i],s);
      for ii:=8-length(s) downto 1 do write(f2,'0');
      write(f2,s);
    end;
  writeln(f2);
end;
begin
  openF;
  read(f1,n,k);
  solve;
  ans;
  closeF;
end.

Code mẫu của hieult

#include <cstdio>
#include <iostream>
//#include <conio.h>
#define base 1000000000

using namespace std;

struct solon
{
     int so;
     long long a[400];
};

int n,k;
solon F[11111],t;

solon tong (solon A,solon B)
{
      int du = 0;
      solon C;
      if(A.so<B.so)
      {
           C = A; 
           A = B;
           B = C;
      }
      for(int i = B.so+1;i<=A.so;i++) B.a[i] = 0;
      C.so = A.so;
      for(int i = 1;i<=A.so;i++)
      {
          C.a[i] = (A.a[i]+B.a[i]+du)%base;
          du = (A.a[i]+B.a[i]+du)/base;
      }
      if(du>0) {C.so++; C.a[C.so] = du;}
      return C;
}

solon tichnho(solon A,long long k,int chuso)
{
      solon C;
      long long du = 0;
      C.so = A.so+chuso;
      for(int i = 1;i<=chuso;i++)
           C.a[i] = 0;
      for(int i = chuso+1;i<=chuso+A.so;i++)
      {
           C.a[i] = (A.a[i-chuso]*k+du)%base;
           du = (A.a[i-chuso]*k+du)/base;
      }
      if(du>0) {C.so++; C.a[C.so] = du;}
      return C;
}

solon tich2(solon A){
      solon C;
      int du = 0;
      C.so = A.so;
      for(int i = 1;i<=A.so;i++){
            C.a[i] = (A.a[i]*2+du);
            if(C.a[i]>=base){
                   C.a[i]-=base;
                   du = 1;
            }
            else du = 0; 
      }
      if(du>0) {C.so++; C.a[C.so] = du;}
      return C; 
}

solon tich(solon A,solon B)
{
      solon C;
      C.so = 1; C.a[1] = 0;
      for(int i = 1;i<=B.so;i++)
      {
           C = tong(C,tichnho(A,B.a[i],i-1));
      }
      return C;
}

void print(solon A)
{
      printf("%lld",A.a[A.so]);
      for(int i = A.so-1;i>=1;i--)
          printf("%09lld",A.a[i]);
}

solon hieu(solon A,solon B){
      solon C; C.so = A.so;
      for(int i = B.so+1;i<=A.so;i++)
           B.a[i] = 0;
      int du = 0;
      for(int i = 1;i<=A.so;i++){
           C.a[i] = A.a[i]-B.a[i]-du;
           if(C.a[i]<0){
                C.a[i]+=base;
                du = 1;
           }
           else du = 0;  
      }
      while(C.a[C.so]==0) C.so--;
      if(C.so==0) C.so = 1; 
      return C;
}

solon Hieu(solon A,solon B){
      solon C; C.so = A.so;
      int du = 0;
      for(int i = 1;i<=A.so;i++){
           if(i>B.so) B.a[i] = 0;
           if(i>t.so) t.a[i] = 0;
           C.a[i] = A.a[i]-B.a[i]+t.a[i]-du;
           if(C.a[i]<0){
                C.a[i]+=base;
                du = 1;
           }
           else if(C.a[i]>=base){
                C.a[i]-=base;
                du = -1;
           }
           else du = 0;  
      }
      if(du == -1) C.a[++C.so] = 1;
      while(C.a[C.so]==0) C.so--;
      if(C.so==0) C.so = 1; 
      return C;
}



int main()
{
      scanf("%d %d",&n,&k);
      t.so = 1; t.a[1] = 1;
      for(int i = 0;i<=n;i++){
            if(i<k){
                  F[i].so = 1 ;
                  F[i].a[1] = 0;
            }
            else if(i==k) {
                  F[i].so = 1;
                  F[i].a[1] = 1;
            }
            else{
                  F[i] = Hieu(tich2(F[i-1]),F[i-k-1]);
                  t = tich2(t);
            }
      }
      print(F[n]);
    //  getch();
}

Code mẫu của khuc_tuan

import java.util.*;
import java.math.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        BigInteger[] F = new BigInteger[n+1];
        F[0] = BigInteger.ONE;
        BigInteger total = BigInteger.ONE;
        for(int i=1;i<=n;++i) {

            F[i] = total;
            if(i<k) F[i] = F[i].add(BigInteger.ONE);

            total = total.add( F[i]);
            if(i>=k) total = total.subtract(F[i-k]);
        }
        BigInteger res = BigInteger.ONE;
        for(int i=0;i<n;++i) res = res.multiply(BigInteger.valueOf(2));
        System.out.println(res.subtract(F[n]));
    }
}