## Editorial for Đếm chuỗi đối xứng

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

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


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