BRACKET - Dãy ngoặc
Tác giả: flashmt
Ngôn ngữ: Pascal
var n,kk:longint;
a:array[0..61] of longint;
b:array[0..1,0..61,-1..31] of qword;
c:array[0..61,-1..31] of qword;
res,re:qword;
procedure rf;
var i,t:longint; c:char;
begin
readln(n,kk);
t:=0;
for i:=1 to n do
begin
read(c);
if c='(' then inc(t) else dec(t);
a[i]:=t;
end;
end;
procedure calc(z:longint);
var i,j,t,k:longint;
begin
b[z,0,0]:=1; k:=kk-z;
if k<1 then exit;
for i:=1 to n div 2 do
begin
for j:=0 to i do
begin
if j<k then t:=j else t:=k;
b[z,i,t]:=b[z,i-1,t-1]+b[z,i-1,t+1];
end;
end;
for i:=n div 2 + 1 to n do
begin
for j:=0 to n-i do
begin
if j<k then t:=j else t:=k;
b[z,i,t]:=b[z,i-1,t-1]+b[z,i-1,t+1];
end;
end;
end;
procedure pr;
var i,j,k:longint; kt:boolean;
begin
fillchar(b,sizeof(b),0);
calc(1); calc(0);
for i:=0 to n do
for j:=0 to kk do
c[i,j]:=b[0,i,j]-b[1,i,j];
re:=c[n,0];
k:=1; res:=0;
kt:=false;
for i:=n-2 downto 2 do
begin
j:=a[n-i];
if j>k then
begin
if not kt then res:=res+c[i,k-1]
else res:=res+b[0,i,k-1];
end;
if j=kk then kt:=true;
k:=j;
end;
end;
procedure wf;
begin
writeln(re);
writeln(re-res);
end;
begin
rf;
pr;
wf;
end.