基础代码

在 1100 ms 波动

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300;
const int MOD = 998244353;
int n;
string s;
// f[i][rg][rb][bg]
// 前 i 个字符，有多少种方案可以使得除了已经消耗的还多了：
// rg 个红绿左括号、rb 个红蓝左括号、bg 个 蓝绿左括号
int now, nxt; // 滚动数组优化掉 f 第一维
// 显然超过了一半的是左括号时就不用管了，后面不可能合法
int f[2][MAXN / 2 + 5][MAXN / 2 + 5][MAXN / 2 + 5];

// 让 a 在原本基础上增加 b，然后再对 MOD 取余
void add(int &a, int &b)
{
    a += b;
    if (a >= MOD)
        a -= MOD;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    cin >> s;

    // 用填表法比较方便（有效状态推出后续状态）
    now = 0, nxt = 1;
    f[now][0][0][0] = 1; // 初始状态
    for (int i = 0; i <= n - 1; i++)
    {
        // 由 f[i(now)][][][] 填出 f[i+1(nxt)][][][]
        // 此时最多只会贡献出 i 个左括号
        // 此时也最多只需要 n-i 个左括号（不然右边就不可能消耗完）
        for (int rg = 0; rg <= min(i, n - i); rg++)
            for (int rb = 0; rb <= min(i, n - i); rb++)
                for (int bg = 0; bg <= min(i, n - i); bg++)
                {
                    if (s[i] != '(')
                    {
                        // 此时可以看作是 )，可以考虑是哪种颜色，来消耗对应颜色的左括号
                        if (rg > 0 && rb > 0)
                            add(f[nxt][rg - 1][rb - 1][bg], f[now][rg][rb][bg]);
                        if (rb > 0 && bg > 0)
                            add(f[nxt][rg][rb - 1][bg - 1], f[now][rg][rb][bg]);
                        if (rg > 0 && bg > 0)
                            add(f[nxt][rg - 1][rb][bg - 1], f[now][rg][rb][bg]);
                    }
                    if (s[i] != ')')
                    {
                        add(f[nxt][rg + 1][rb + 1][bg], f[now][rg][rb][bg]);
                        add(f[nxt][rg][rb + 1][bg + 1], f[now][rg][rb][bg]);
                        add(f[nxt][rg + 1][rb][bg + 1], f[now][rg][rb][bg]);
                    }
                }
        // 滚动数组，并给下一层清空
        swap(now, nxt);
        for (int rg = 0; rg <= n / 2; rg++)
            for (int rb = 0; rb <= n / 2; rb++)
                for (int bg = 0; bg <= n / 2; bg++)
                    f[nxt][rg][rb][bg] = 0;
    }
    cout << f[now][0][0][0];
    return 0;
}

加了些无解状态的优化，但是结果跑的似乎更慢了（

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300;
const int MOD = 998244353;
int n;
string s;
int now, nxt;
int f[2][MAXN / 2 + 5][MAXN / 2 + 5][MAXN / 2 + 5];

void add(int &a, int &b)
{
    a += b;
    if (a >= MOD)
        a -= MOD;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    cin >> s;

    now = 0, nxt = 1;
    f[now][0][0][0] = 1;
    for (int i = 0; i <= n - 1; i++)
    {
        for (int rg = 0; rg <= min(i, n - i); rg++)
            for (int rb = 0; rb <= min(i, n - i); rb++)
                // 三个相加的结果就是三种颜色括号数量的两倍，必然是偶数
                for (int bg = (rg + rb) % 2; bg <= min(i, n - i); bg += 2)
                {
                    // 如果当前状态不可能达成最终 rg, rb, bg 清空，那也不用管当前状态了
                    // 当前的左括号总数就是 (rg + rb + bg) / 2，当前都不行，更多左括号就更不行了
                    if ((rg + rb + bg) / 2 > n - i)
                        break;
                    if (s[i] != '(')
                    {
                        if (rg > 0 && rb > 0)
                            add(f[nxt][rg - 1][rb - 1][bg], f[now][rg][rb][bg]);
                        if (rb > 0 && bg > 0)
                            add(f[nxt][rg][rb - 1][bg - 1], f[now][rg][rb][bg]);
                        if (rg > 0 && bg > 0)
                            add(f[nxt][rg - 1][rb][bg - 1], f[now][rg][rb][bg]);
                    }
                    if (s[i] != ')')
                    {
                        add(f[nxt][rg + 1][rb + 1][bg], f[now][rg][rb][bg]);
                        add(f[nxt][rg][rb + 1][bg + 1], f[now][rg][rb][bg]);
                        add(f[nxt][rg + 1][rb][bg + 1], f[now][rg][rb][bg]);
                    }
                }
        swap(now, nxt);
        for (int rg = 0; rg <= n / 2; rg++)
            for (int rb = 0; rb <= n / 2; rb++)
                for (int bg = 0; bg <= n / 2; bg++)
                    f[nxt][rg][rb][bg] = 0;
    }
    cout << f[now][0][0][0];
    return 0;
}