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=121;
      base=100000000;
      digit=8;
type bignum=array[0..10] of longint;
var n:longint;
    s:string;
    f:array[1..maxn,1..maxn] of bignum;

procedure rf;
var i:longint;
begin
     assign(input,fi);
     reset(input);
     read(s);
     n:=length(s);
     fillchar(f,sizeof(f),0);
     close(input);
end;

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

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

procedure calc(l,r:longint);
var t:bignum;
begin
     if l=r then
     begin
          f[l,l,0]:=1; f[l,l,1]:=1;
          exit;
     end;
     if f[l,r-1,0]=0 then calc(l,r-1);
     if f[l+1,r,0]=0 then calc(l+1,r);
     plus(f[l,r],f[l,r-1],f[l+1,r]);
     if s[l]=s[r] then
     begin
          fillchar(t,sizeof(t),0);
          t[0]:=1; t[1]:=1;
          plus(f[l,r],f[l,r],t);
     end
     else
     begin
          if (l+1<=r-1) and (f[l+1,r-1,0]=0) then calc(l+1,r-1);
          minus(f[l,r],f[l+1,r-1]);
     end;
end;

procedure pr;
var i,j:longint;
begin
     calc(1,n);
end;

procedure wf;
var i,j,t:longint; s:string; re:bignum;
begin
     assign(output,fo);
     rewrite(output);
     re:=f[1,n];
     for i:=re[0] downto 1 do
     begin
          if i<re[0] then
          begin
               str(re[i],s);
               t:=length(s);
               for j:=t+1 to digit do write(0);
          end;
          write(re[i]);
     end;
     close(output);
end;

begin
     rf;
     pr;
     wf;
end.

Code mẫu của happyboy99x

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

const int BASE = 1000000000, MAX_DIGIT = 5, LOG_BASE = 9, N = 120;
struct BigInteger {
    int d[MAX_DIGIT], n;

    void operator = (const int &x) {
        memset(d, 0, sizeof d); n = 0;
        for(int t = x; t != 0; t /= BASE)
            d[n++] = t % BASE;
    }

    void operator += (const BigInteger &a) {
        int rem = 0; n = max(n, a.n);
        for(int i = 0; i < n; ++i) {
            int p = d[i] + a.d[i] + rem;
            if(p >= BASE) d[i] = p - BASE, rem = 1;
            else d[i] = p, rem = 0;
        }
        if(rem) d[n++] = rem;
    }

    void operator -= (const BigInteger &a) {
        int rem = 0;
        for(int i = 0; i < n; ++i) {
            int p = d[i] - a.d[i] - rem;
            if(p < 0) d[i] = p + BASE, rem = 1;
            else d[i] = p, rem = 0;
        }
        while(n > 0 && d[n-1] == 0) --n;
    }

    void print() {
        printf("%d", d[n-1]);
        for(int i = n-2; i >= 0; --i)
            printf("%0*d", LOG_BASE, d[i]);
        printf("\n");
    }
} f[N][N], ONE;
char s[N+1];

int main() {
    ONE = 1; scanf("%s", s); int n = strlen(s);
    for(int i = 0; i < n; ++i) f[i][i] = ONE;
    for(int l = 2; l <= n; ++l)
        for(int i = 0, j = l - 1; j < n; ++i, ++j) {
            f[i][j] = f[i+1][j];
            f[i][j] += f[i][j-1];
            if(s[i] == s[j]) f[i][j] += ONE;
            else f[i][j] -= f[i+1][j-1];
        }
    f[0][n-1].print();
    return 0;
}

Code mẫu của ladpro98

program qbpal;
uses    math;
type    big=string;

const   fi='';
var     s:string;
        f:array[1..123,1..123] of big;
        check:array[1..123,1..123] of boolean;
        n:longint;

procedure input;
var     inp:text;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,s);
        close(inp);
        n:=length(s);
end;

function plus(a,b:big):big;
var     c:big;
        i,carry,s:longint;
begin
        carry:=0;c:='';
        while  length(a)<length(b) do a:='0'+a;
        while  length(b)<length(a) do b:='0'+b;
        for i:=length(a) downto 1 do
        begin
                s:=ord(a[i])+ord(b[i])+carry-96;
                c:=chr(s mod 10+48) +c;
                carry:=s div 10;
        end;
        if carry>0 then c:='1'+c;
        exit(c);
end;

function sub(a,b:big):big;
var     c:big;
        s,br,i:longint;
begin
        br:=0;
        c:='';
        while  length(a)<length(b) do a:='0'+a;
        while  length(b)<length(a) do b:='0'+b;
        for i:=length(a) downto 1 do
        begin
                s:=ord(a[i])-ord(b[i])-br;
                if s<0 then
                begin
                        s:=s+10;
                        br:=1;
                end
                else
                br:=0;
                c:=chr(s+48)+c;
        end;
        while (length(c)>1) and (c[1]='0') do delete(c,1,1);
        exit(c);
end;

procedure init;
var     i,j:longint;
begin
        for i:=1 to n do
        begin
                f[i,i]:='1';
                check[i,i]:=true;
        end;
        for i:=1 to n-1 do
        begin
                if s[i]=s[i+1] then
                begin
                        f[i,i+1]:='3';
                        check[i,i+1]:=true;
                end
                else
                begin
                        f[i,i+1]:='2';
                        check[i,i+1]:=true;
                end;
        end;
end;

function dp(i,j:longint):big;
var     k:longint;
begin
        if check[i,j] then exit(f[i,j]);
        check[i,j]:=true;
        if s[i]=s[j] then
        f[i,j]:=plus(plus(dp(i+1,j),dp(i,j-1)),'1')
        else
        f[i,j]:=sub(plus(dp(i+1,j),dp(i,j-1)),dp(i+1,j-1));
        exit(f[i,j]);
end;

begin
        input;
        init;
        write(dp(1,n));
end.

Code mẫu của RR

{$R+,Q+}
uses math;
const
  MAXN=200;
  oo=10;
type
  bigNum=array[0..MAXN] of longint;
var
  s:string;
  n:longint;
  d:array[0..MAXN,0..MAXN] of bigNum;
operator +(a,b:bigNum) c:bigNum;
var
  nho,i:longint;
begin
  nho:=0;
  fillchar(c,sizeof(c),0); c[0]:=max(a[0],b[0]);
  for i:=MAXN downto MAXN-c[0]+1 do
    begin
      c[i]:=a[i]+b[i]+nho;
      nho:=c[i] div oo;
      c[i]:=c[i] mod oo;
    end;
  if nho>0 then
    begin
      inc(c[0]);
      c[MAXN-c[0]+1]:=nho;
    end;
end;
operator -(a,b:bigNum) c:bigNum;
var
  nho,i:longint;
begin
  nho:=0;
  fillchar(c,sizeof(c),0); c[0]:=a[0];
  for i:=MAXN downto MAXN-c[0]+1 do
    begin
      c[i]:=a[i]-b[i]-nho;
      if c[i]<0 then
        begin
          nho:=1;
          c[i]:=c[i]+oo;
        end
      else nho:=0;
    end;
  while (c[0]>0) and (c[MAXN-c[0]+1]=0) do dec(c[0]);
end;
procedure solve;
var
  i,j,k:longint;
  a:bigNum;
begin
  fillchar(a,sizeof(a),0);
  a[0]:=1; a[200]:=1;
  for i:=1 to n do d[i,i]:=a;
  for k:=1 to n do
  for i:=1 to n-k do
    begin
      j:=i+k;
      if s[i]=s[j] then d[i,j]:=d[i,j-1]+d[i+1,j]+a
      else d[i,j]:=d[i,j-1]+d[i+1,j]-d[i+1,j-1];
    end;
end;
procedure print(a:bigNum);
var
  i:longint;
  s:string;
begin
  if a[0]=0 then begin writeln(0); exit; end;
  write(a[MAXN-a[0]+1]);
  for i:=MAXN-a[0]+2 to MAXN do write(a[i]);
  writeln;
end;
begin
  readln(s); n:=length(s);
  solve;
  print(d[1,n]);
end.

Code mẫu của hieult

#include <cstdio>
#include <cstring>
//#include <conio.h>
#define base 100000000

struct solon
{
     int so;
     int a[40];
};

solon f[122][122],T;
char s[122];
int n;

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 hieu(solon A,solon B)
{
      int du = 0;
      solon 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);
           if(C.a[i]<0) {
                   C.a[i] += base;
                   du = 1;
           }
      }
      while(C.a[C.so]==0 && C.so>1) C.so--;
      return C;
}

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

bool doixung(int i,int j)
{
     if(j-i<2)
         return (s[i]==s[j]);
     if(s[i]!=s[j]) return false;
     else return doixung(i+1,j-1);
}

int main()
{
     // freopen("QBPAL.in","r",stdin);
      scanf("%s",s);
      n = strlen(s);
      T.so = 1; T.a[1] = 1;
      for(int i = 0;i<n;i++)
      {
           f[i][i] = T;
           f[i+1][i].so = 1;
           f[i+1][i].a[1] = 0;
      }
      for(int k = 1;k<n;k++)
           for(int i =0;i+k<n;i++)
           {
                int j = i+k;
                f[i][j] = tong(f[i+1][j],f[i][j-1]);
                if(s[i]==s[j]) f[i][j] = tong(f[i][j],T);
                else f[i][j] = hieu(f[i][j],f[i+1][j-1]); 
              //  printf("%d %d %d\n",i,j,f[i][j].a[1]);
           }
      //if(doixung(0,n-1)) f[0][n-1] = hieu(f[0][n-1],T);
      print(f[0][n-1]);  
    //  getch(); 
}

Code mẫu của khuc_tuan

s = raw_input()
n = len(s)

F = [[-1 for i in range(n)] for j in range(n)]

def calc(a,b):
    if a>b:
        return 1
    if a==b:
        return 2
    if F[a][b]!=-1:
        return F[a][b]
    res = 0
    res = calc(a+1,b) + calc(a,b-1) - calc(a+1,b-1)
    if s[a]==s[b]:
        res += calc(a+1,b-1)
    F[a][b] = res
    return res

print calc(0,n-1) - 1