经典状压DP

首先如果所有的S中的左括号和右括号数量不一样，无论如果都无法拼成一个合法括号序列。然后开始状压DP，我们令dp[mask]表示为掩码mask为1的字符串已经被选取的方案数，那么答案就是dp[(1 << n) - 1]。

那么转移也很显然，对于一个v在当前mask中没有被选取，同时这个字符串可以接在当前mask后面那么就可以转移为dp[mask | (1 << v)] += dp[mask]

现在我们考虑什么是合法的转移。

对于一个合法括号序列，首先每一位上前缀的“（” 不少于 “）” 的数量，同时总共的（ 和 ） 数量相等即可

那么我们对于每个字符串可以用一个数字记录 （ 的数量 减去 ）的数量，这个这个数字>=0 那么就是合法的，这个数字后文用cnt表示。

如果你认为转移的时候，只要当前mask里的cnt + 不在mask 里的 v 的cnt >=0 那就错了，一个简单的反例就是 比如前缀是 ((()) 后面不能接 )))(((( ，虽然前面的cnt > 0 后面的 cnt > 0 但是显然 ((()))))((((是不合法的。

那么怎么解决呢

我们只需要记录前缀中cnt最小值就行了，只要mask的cnt + 接上的字符串的 cnt前缀最小值 >= 0，显然可以拼接，不难看出这个条件是可以拼接的等价条件。

时间复杂度O(n*2^n)

(打的时候猪逼了一开始写了个n方2^n的😭)

贴上AC代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;
constexpr int MOD = 1e9 + 7, INF = 1e18;
void solve()
{
    int n;
    cin >> n;
    int cnt = 0;
    vector<int> a(n);//每个字符串（ - ）的数量差
    vector<int> b(n, INF);// 每个数量差的最小值
    for (int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        int sum = 0;
        for (auto c: s)
        {
            if (c == '(') sum++;
            else sum--;
            b[i] = min(b[i], sum);
        }
        a[i] = sum;
        cnt += sum;
    }
    if (cnt != 0)
    {
        cout << "0\n";//判掉不合法
        return;
    }
    const int FULL = 1ll << n;
    vector dp(FULL, 0);
    dp[0] = 1;
    for (int mask = 0; mask < FULL; mask++)
    {
        if (!dp[mask]) continue;
        int sum = 0;//当前的差值
        for (int u = 0; u < n; u++)
        {
            if (mask >> u & 1) sum += a[u];
        }
        for (int v = 0; v < n; v++)
        {
            if (mask >> v & 1) continue;
            if (b[v] + sum < 0) continue;// 不合法转移判掉
            dp[mask | (1ll << v)] = (dp[mask | (1ll << v)] + dp[mask]) % MOD;
        }
    }
    cout << dp[FULL - 1] << '\n';
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int __ = 1;
    cin >> __;
    while (__--)
    {
        solve();
    }
    return 0;
}