QBPAL - Đếm chuỗi đối xứng
Tác giả: RR
Ngôn ngữ: Pascal
{$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.