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

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.

Code mẫu của happyboy99x

#include<cstdio>

const int N = 60 + 2;
long long f[N][N/2][2];
int n, k;
char s[N];

void dp() {
    f[n][0][0] = 1;
    for(int x = n; x > 0; --x)
        for(int y = k; y >= 0; --y)
            for(int c = 0; c <= 1; ++c) {
                if(y > 0) f[x-1][y-1][c] += f[x][y][c];
                if(y < k) f[x-1][y+1][(y+1==k)|c] += f[x][y][c];
            }
}

long long order(char * s) {
    long long res = 1;
    int preH = 0, h = 0;
    bool c = false;
    for(int i = 0; i < n; ++i) {
        h += s[i] == '(' ? 1 : -1;
        if(h < preH && h + 2 <= k) {
            res += f[i+1][h+2][1];
            if(c) res += f[i+1][h+2][0];
        }
        c |= h == k; preH = h;
    }
    return res;
}

int main() {
    scanf("%d%d%s", &n, &k, s);
    dp();
    printf("%lld\n%lld\n", f[0][0][1], order(s));
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>
const int N = 66;
using namespace std;
string s;
long long F[N][N][N], G[N][N][2][N];
int n, d;

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> d; cin >> s;
    G[n][0][0][0] = 1;
    for(int i = n; i; i--)
    for(int j = 0; j <= d; j++)
    for(int k = 0; k <= d; k++)
    if (G[i][j][0][k] || G[i][j][1][k]) {
        F[i][j][k] = G[i][j][0][k] + G[i][j][1][k];
        G[i - 1][j + 1][1][max(k, j + 1)] += F[i][j][k];
        if (j) G[i - 1][j - 1][0][k] += F[i][j][k];
    }
    cout << G[0][0][0][d] << endl;
    int deg = 0; long long res = 1; bool passed = false;
    for(int i = 0; i < n; i++) {
        if (s[i] == ')') {
            if (passed) res += accumulate(G[i][deg][0], G[i][deg][0] + d + 1, 0);
            else
                res += G[i][deg][0][d];
        }
        if (s[i] == '(') deg++; else deg--;
        if (deg == d) passed = true;
    }
    cout << res << endl;
    return 0;
}

Code mẫu của RR

const   fi='';
        fo='';
        maxn=61;
type    mang=array[0..maxn,-1..maxn] of int64;
var     f:text;
        n,k,i,j,l,t:longint;
        sl1,sl2:mang;
        s:string;
        res1,res2:int64;
procedure doc;
begin
  assign(f,fi);
  reset(f);
  readln(f,n,k);
  readln(f,s);
  close(f);
end;
function min(a,b:longint):longint;
begin
  if a<b then exit(a) else exit(b);
end;
procedure tinh(b:longint;var sl:mang);
var i,j:longint;
begin
  sl[0,0]:=1;
  for i:=1 to n do
    for j:=0 to b do
      sl[i,j]:=sl[i-1,j-1]+sl[i-1,j+1];
end;
procedure xuli1;
begin
  tinh(k,sl1);tinh(k-1,sl2);
  res1:=sl1[n,0]-sl2[n,0];
end;
procedure xuli2;
begin
  t:=0;
  for i:=1 to n do
    begin
      if s[i]='(' then inc(t) else dec(t);
      if s[i]=')' then res2:=res2+sl1[n-i,t+2];
    end;
  for i:=1 to n do
    begin
      if s[i]='(' then inc(t) else dec(t);
      if t=k then break;
      if s[i]=')' then res2:=res2-sl2[n-i,t+2];
    end;
end;
procedure ghi;
begin
  assign(f,fo);
  rewrite(f);
  writeln(f,res1);
  writeln(f,res2+1);
  close(f);
end;
begin
  doc;
  xuli1;
  xuli2;
  ghi;
end.

Code mẫu của hieult

#include <cstdio>
#include <cstring>
//#include <conio.h>
#include <iostream>

    long long n,k,a[62],m;
    long long f[62][62],g[62][62];
    char s[62];

using namespace std;

int main()
{
    //freopen("BRACKET.in","r",stdin);

    scanf("%lld %lld",&n,&k);
   // printf("%d %d\n",'(',')');
    scanf("%s",s);
    a[0] = 0;
    int t = 0;
    for(int i  = 0;i<n;i++)
    {
            t++;
            if(s[i]=='(') a[t] = a[t-1]+1;
            else if(s[i]=')') a[t] = a[t-1]-1;
    }
    memset(f,0,sizeof(f));memset(g,0,sizeof(g));
    f[n][0] = 1;
    g[n][0] = 1;
    for(int i = n-1;i>=0;i--)
    {
         f[i][0] = f[i+1][1];
         for(int j = 1;j<=k;j++)
             f[i][j] = f[i+1][j-1]+f[i+1][j+1];
         //printf("%d\n",f[i][0]);
    }
    for(int i = n-1;i>=0;i--)
    {
         g[i][0] = g[i+1][1];
         for(int j = 1;j<=k-1;j++)
             g[i][j] = g[i+1][j-1]+g[i+1][j+1];
        // printf("%d\n",g[i][0]);
    }
    printf("%lld\n",f[0][0]-g[0][0]);
    long long kq = 1,kq1=0;
    for( t=0;t<=n-1;t++)
    {
        if(a[t+1]<a[t] && a[t]<k)
            kq1 += f[t+1][a[t]+1]-g[t+1][a[t]+1];
        if(a[t]==k)
            break;
    }
    for( ;t<=n-1;t++)
        if(a[t+1]<a[t] && a[t]<k)
            kq1 += f[t+1][a[t]+1];
    //printf("%lld %lld %lld\n",f[0][0],g[0][0],kq);
    printf("%lld",kq1+1);
   // getch();

}