A47434 正经题解

题意分析
给定一个字符串中的一些字符和一些未知字符，求有多少种可能使其成为“符合规范的超级括号序列”，答案对$10^9+7$取模。
“符合规范的超级括号序列”的定义如下：
1、()、(S) 均是符合规范的超级括号序列，其中 S 表示任意一个仅由不超过 k 个字符 * 组成的非空字符串（以下两条规则中的 S 均为此含义。
2、如果字符串 A 和 B 均为符合规范的超级括号序列，那么字符串 AB、ASB 均为符合规范的超级括号序列，其中 AB 表示把字符串 A 和字符串 B 拼接在一起形成的字符串；
3、如果字符串 A 为符合规范的超级括号序列，那么字符串 (A)、(SA)、(AS) 均为符合规范的超级括号序列。
4、所有符合规范的超级括号序列均可通过上述 3 条规则得到。
关键观察
因为是括号序列，且字符串长度$n<=500$，所以睁眼法可得这是一道区间dp问题。但是题目中给定的星号大大加大了该题难度，直接进行转移方程设计极其困难，而且基本不可能不算重，于是我们想到可以多加一维，空间紧张，再开一维只能是小数字了，这一维要表示什么呢？
通过观察“符合规范的超级括号序列”的定义我们可知，可形成新“符合规范的超级括号序列”的方式较少，我们依次建立动规数组：
$dp[l][r][s]$表示区间$[l, r]$中$s$状态的数量，
状态0表示全为*，
状态1表示定义中的()、(S) ，
状态2表示所有的合法序列（状态1加上枚举分割求出的AB、ASB），
状态3表示AS（通过状态2和状态0数量计算），
状态4表示SA（通过状态2和状态0数量计算），
（状态不一定需要合法，因为这其中的状态都是为状态2的计算服务的。）
根据这些状态，我们一步步推出正确答案$dp[1][n][2]$，即区间$[1, n]$中的“符合规范的超级括号序列”数量。
（下标做了+1处理方便烧烤，记得取模）
AC代码

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
long long dp[505][505][5];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n, k;
    string s;
    cin >> n >> k;
    cin >> s;
    s = " "+s; //让计算从下标1开始，更方便
    for(int i=1;i<=n;++i)
        dp[i][i-1][0] = 1;
    for(int len=1;len<=n;++len){
        for(int l=1;l+len-1<=n;++l){
            int r = l+len-1;
            if(len<=k){
                if(len==1){
                    if(s[l]=='*'||s[l]=='?')
                        dp[l][r][0] = 1;
                }else{
                    if(dp[l][r-1][0]&&(s[r]=='*'||s[r]=='?'))
                        dp[l][r][0] = 1;
                }
            }
            if(len>=2){
                if((s[l]=='('||s[l]=='?')&&(s[r]==')'||s[r]=='?'))
                    dp[l][r][1] = (dp[l+1][r-1][0]+dp[l+1][r-1][2]+dp[l+1][r-1][3]+dp[l+1][r-1][4])%MOD;
                for(int mid=l;mid<r;++mid){
                    dp[l][r][2] = (dp[l][r][2]+(dp[l][mid][2]+dp[l][mid][3])*dp[mid+1][r][1])%MOD;
                    dp[l][r][3] = (dp[l][r][3]+dp[l][mid][2]*dp[mid+1][r][0])%MOD;
                    dp[l][r][4] = (dp[l][r][4]+dp[l][mid][0]*dp[mid+1][r][2])%MOD;
                }
            }
            dp[l][r][2] = (dp[l][r][2]+dp[l][r][1])%MOD;
        }
    }
    cout << dp[1][n][2]%MOD;
    
    return 0;
}

时间复杂度
$O(n^3)$，但循环中操作仅仅是几行简单的数学运算，常数因子较小，加上acgo神机一秒跑完1e9的神力，该代码实际并不会TLE。
（这已经是不死凹常数因子的最快方法了吧，目前没有任何已知的$O(n^2)$或$O(n^2 \log n)$解法）