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='';
      maxn=210;
      base=100000;
var n:longint;
    a:string;
    b:array['('..'}','('..'}'] of longint;
    f:array[0..maxn,0..maxn] of int64;
    g:array[0..maxn,0..maxn] of boolean;

procedure rf;
begin
     readln(n);
     readln(a);
     b['(',')']:=1; b['{','}']:=1; b['[',']']:=1;
     b['(','?']:=1; b['{','?']:=1; b['[','?']:=1;
     b['?',')']:=1; b['?','}']:=1; b['?',']']:=1;
     b['?','?']:=3;
end;

procedure wf0(re:int64);
var s:string; i,l:longint;
begin
     str(re,s);
     l:=length(s);
     for i:=l+1 to 5 do write(0);
end;

procedure pr;
var i,j,k,l:longint;
begin
     for i:=1 to n-1 do f[i+1,i]:=1;
     for l:=1 to n shr 1 do
         for i:=1 to n-l shl 1+1 do
         begin
              j:=i+l shl 1-1;
              if (a[j]='(') or (a[j]='[') or (a[j]='{') then continue;
              if (a[i]=')') or (a[i]=']') or (a[i]='}') then continue;
              f[i,j]:=f[i+1,j-1]*b[a[i],a[j]];
              g[i,j]:=g[i+1,j-1] or (f[i,j]>=base);
              f[i,j]:=f[i,j] mod base;
              for k:=i+1 to j-2 do
              begin
                   f[i,j]:=f[i,j]+f[i+1,k-1]*f[k+1,j]*b[a[i],a[k]];
                   g[i,j]:=g[i,j] or (f[i,j]>=base);
                   f[i,j]:=f[i,j] mod base;
              end;
         end;
     if g[1,n] then wf0(f[1,n]);
     writeln(f[1,n]);
end;

begin
     assign(input,fi); reset(input);
     rf;
     pr;
     close(input);
end.

Code mẫu của ladpro98

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <fstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define REP(i, a, b) for(int i = (a); i <=(b); ++i)
#define REPD(i, a, b) for(int i = (a); i >=(b); --i)
#define TR(it, a) for(typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
#define RESET(a, v) memset(a, (v), sizeof(a))
#define SZ(a) (int(a.size()))
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define long long long
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
#define VII vector<II>
#define endl '\n'

const int N = 222;
const int MOD = 100000;

using namespace std;

int n;
long f[N][N][2];
char s[N];
bool bigNumber;

bool unknown(char c) {
    return c == '?';
}

bool isOpen(char c) {
    return c == '(' || c == '[' || c == '{';
}

bool isClose(char c) {
    return c == ')' || c == ']' || c == '}';
}

bool match(char a, char b) {
    return (a == '(' && b == ')') ||
           (a == '[' && b == ']') ||
           (a == '{' && b == '}');
}

long dp(int l, int r, bool wrap) {
    long &ans = f[l][r][wrap];
    if (ans != -1) return ans;
    ans = 0;
    if (!((r - l) & 1)) return 0;
    if (l > r) return ans = 1;
    bool L = unknown(s[l]), R = unknown(s[r]);
    if ((!L && !R && match(s[l], s[r])) ||
        (L != R && (isOpen(s[l]) || isClose(s[r]))))
        ans += dp(l + 1, r - 1, 0);
    else if (L && R)
        ans += dp(l + 1, r - 1, 0) * 3;
    if (ans >= MOD) {
        bigNumber = 1;
        ans %= MOD;
    }
    if (wrap) return ans;
    FOR(i, l + 1, r - 1) {
        ans += dp(l, i, 1) * dp(i + 1, r, 0);
        if (ans >= MOD) {
            bigNumber = 1;
            ans %= MOD;
        }
    }
    return ans;
}

int main() {
    #ifdef _LAD_
        freopen("MREPLBRC.in", "r", stdin);
    #endif // _LAD_
    scanf("%d\n%s", &n, s);
    RESET(f, -1);
    int ans = dp(0, n - 1, 0);
    if (bigNumber)
        printf("%05d", ans);
    else
        printf("%d", ans);
    return 0;
}

Code mẫu của RR

#include <iostream>
#include <algorithm>
#define FOR(i,a,b) for(long i=a; i<=b; i++)
#define DOWN(i,a,b) for(long i=a; i>=b; i--)
#define BASE 100000
using namespace std;

long long f[211][211];
long n,ok[211][211];
char a[211];

void inp() {
    scanf("%ld\n",&n);
    gets(a);
}

long nway(long i,long j) {
    if (a[i]==')' || a[i]==']' || a[i]=='}') return 0L;
    if (a[j]=='(' || a[j]=='[' || a[j]=='{') return 0L;

    if (a[i]=='?' && a[j]=='?') return 3;
    if (a[i]=='?' || a[j]=='?') return 1;

    if (a[i]=='(' && a[j]!=')') return 0;
    if (a[i]=='[' && a[j]!=']') return 0;
    if (a[i]=='{' && a[j]!='}') return 0;

    return 1;
}

void solve() {
    n--;
    FOR(i,1,n) f[i][i-1]=1;
    FOR(i,0,n-1) f[i][i+1]=nway(i,i+1);
    FOR(l,4,n+1)
    if (!(l&1))
    FOR(i,0,n-l+1) {
        long j=i+l-1;
        f[i][j]=f[i+1][j-1]*nway(i,j);
        if (f[i][j]>BASE) {
            ok[i][j]=1;
            f[i][j]=f[i][j]%BASE;
        }
        FOR(k,i+1,j-2) {
            f[i][j]+=f[i+1][k-1]*f[k+1][j]*nway(i,k);
            if (f[i][j]>BASE) {
                f[i][j]%=BASE;
                ok[i][j]=1;
            }
        }
    }
    if (!ok[0][n]) cout<<f[0][n];
    else {
        if (f[0][n]<10) cout<<"0000"<<f[0][n];
        else if (f[0][n]<100) cout<<"000"<<f[0][n];
        else if (f[0][n]<1000) cout<<"00"<<f[0][n];
        else if (f[0][n]<10000) cout<<"0"<<f[0][n];
        else cout<<f[0][n];
    }
}

int main() {
    inp();
    solve();
    return 0;
}

Code mẫu của hieult

#include <cstdio>
#include <iostream>
//#include <conio.h>
#define Max 201
#define du 100000

using namespace std;

long long dongian(long long a)
{
     if(a<du) return a;
     else return (du+a%du);
}
char trai[] = {'(','[','{'};
char phai[] = {')',']','}'};
long long f[Max][Max];
int n;
char s[Max];

long long tinh(int a, int b)
{
     if(a>b) return 1;
     long long t = f[a][b];
     if(t>=0) return t;
     else t = 0;
     for(int i = a+1;i<=b;i+=2)
         for(int j = 0;j<3;j++)
              if(s[a]==trai[j]||s[a]=='?')
                   if(s[i]==phai[j]||s[i]=='?')
                        t = dongian(t+tinh(a+1,i-1)*tinh(i+1,b));
     f[a][b] = t;
     return t;
}

int main()
{
    //freopen("MREPLBRC.in","r",stdin);
    scanf("%d",&n);
    scanf("%s",s);
   // printf("***%s****\n",s);
    memset(f,-1,sizeof(f));
    long long kq = tinh(0,n-1);
    if(kq<du) printf("%lld",kq);
    else printf("%05lld",kq%du);
  //  getch();
}

Code mẫu của khuc_tuan

//{$A8,B-,C+,D+,E-,F-,G+,H+,I+,J-,K-,L+,M-,N+,O+,P+,Q+,R+,S+,T-,U-,V+,W-,X+,Y+,Z1}
// {$APPTYPE CONSOLE}
 {$mode delphi}

uses math;

var
    n : integer;
    a : array[0..400] of char;
    f : array[0..200,0..200] of int64;

function check(a,b : char) : boolean;
begin
    check := ((a='(') and (b = ')')) or
        ((a='[') and (b = ']')) or
        ((a='{') and (b = '}'));
end;

function mo( a : char) : boolean;
begin
    mo := (a='(') or (a='[') or (a='{') or (a='?');
end;
function dong( a : char) : boolean;
begin
    dong := (a=')') or (a=']') or (a='}') or (a='?');
end;

procedure tang(var a : int64; b : int64); 
begin
    inc(a,b);
    if a >= 200000 then
    begin
        a := a mod 100000 + 100000;
    end;
end;

function calc( l, r : integer ) : int64;
var
    i : integer;
begin
    if l > r then
    begin
        calc := 1;
        exit;
    end;
    if l = r then
    begin
        calc := 0;
        exit;
    end;
    if f[l,r]<>-1 then
    begin
        calc := f[l,r];
        exit;
    end;
    f[l,r] := 0;

    for i:=l+1 to r do
        if (check(a[l],a[i])) or ((a[l]='?') and dong(a[i])) or ((a[i]='?') and mo(a[l])) then
        begin
            if (a[l]<>'?') or (a[i]<>'?') then
                   tang( f[l,r], calc(l+1,i-1) * calc(i+1,r))
            else tang( f[l,r], calc(l+1,i-1) * calc(i+1,r) * 3);
        end;

    calc := f[l,r];
end;

var
    res : integer;

begin
    readln(n);
    readln(a);
    move( a[0], a[1], 300);
    fillchar( f, sizeof(f), -1);
    res :=  calc( 1, n) ;
    // writeln(res);
    if res <  100000 then writeln(res)
    else begin
        res := res mod 100000;
        if res < 10000 then write(0);
        if res < 1000 then write(0);
        if res < 100 then write(0);
        if res < 10 then write(0);
        write(res);
    end;
end.