P7914 Solution
先考虑 Subtask \(4\)。设 \(dp_i\) 表示长度为 \(i\) 的方案数，按题目定义转移:
-
AB,ASB：\(\displaystyle dp_n\gets dp_n+\sum_{i=1}^{n-1}\sum_{j=0}^kdp_i\times dp_{n-i-j}\) -
(A)：\(\displaystyle dp_n\gets dp_n+dp_{n-2}\) -
(SA),(AS)：\(\displaystyle dp_n\gets dp_n+2\sum_{i=1}^kdp_{n-k-2}\)
初始化：\(\forall i\in[2,k+2],dp_i\gets1\)。
但是我们注意到形如 ()()()，()*()*()，(**)*()*(**)*(*) 的方案会被算重。
我们发现这些被算重的方案由多个小块加上中间的若干 * （或没有 *）拼成，其中 这些小块都由 (A),(AS),(SA) 转移得来。
那么现在去重就很简单了，例如我们将 ()()() 唯一表示为 ()() + ()，()*()*() 唯一表示为 ()*() + * + ()，(**)*()*(**)*(*) 唯一表示为 (**)*()*(**) + * + (*)，等等。
设 \(dp1_i\) 表示长度为 \(i\)，由 (A),(AS),(SA) 转移得来的方案数，\(dp2_i\) 表示长度为 \(i\) 的总方案数，修改转移方程如下：
-
AB,ASB：\(\displaystyle dp2_n\gets dp2_n+\sum_{i=1}^{n-1}\sum_{j=0}^kdp2_i\times dp1_{n-i-j}\) -
(A)：\(\displaystyle dp1_n\gets dp1_n+dp2_{n-2}\)
\(\displaystyle dp2_n\gets dp2_n+dp2_{n-2}\)
(SA),(AS)：\(\displaystyle dp1_n\gets dp1_n+2\sum_{i=1}^kdp2_{n-k-2}\)
\(\displaystyle dp2_n\gets dp2_n+2\sum_{i=1}^kdp2_{n-k-2}\)
初始化：\(\forall i\in[2,k+2],dp1_i\gets1,dp2_i\gets1\)。
现在来想想 \(\mathcal O(n^4)\) 的做法：我们发现我们的转移涉及两段区间的拼凑，于是很自然地想到了区间 dp。
设 \(dp1_{l,r}\) 表示在 \([l,r]\) 中由 (A),(AS),(SA) 转移得来的方案数，\(dp2_{l,r}\) 表示在 \([l,r]\) 中的总方案数：
（设 \(st_{l,r}\) 表示 \([l,r]\) 中的字符是否全都是 * 或 ?）
-
AB,ASB：\(\displaystyle dp2_{l,r}\gets dp2_{l,r}+\sum_{i=l}^{r-1}\sum_{j=0}^kst_{i+1,i+j}\times dp2_{l,i}\times dp1_{i+j+1,r}\) -
(A)：\(\displaystyle dp1_{l,r}\gets dp1_{l,r}+dp2_{l+1,r-1}\)
\(\displaystyle dp2_{l,r}\gets dp2_{l,r}+dp2_{l+1,r-1}\)
(SA),(AS)：\(\displaystyle dp1_{l,r}\gets dp1_{l,r}+\sum_{i=1}^k(st_{l+1,l+i}\times dp2_{l+i+1,r-1}+st_{r-i,r-1}\times dp2_{l+1,r-i-1})\)
\(\displaystyle dp2_{l,r}\gets dp2_{l,r}+\sum_{i=1}^k(st_{l+1,l+i}\times dp2_{l+i+1,r-1}+st_{r-i,r-1}\times dp2_{l+1,r-i-1})\)
初始化：\(\forall r-l\le k+2\)，若 \(s_l\) 为 ( 或 *，\(s_r\) 为 ) 或 * 且 \(st_{l+1,r-1}=1\) 则 \(dp_{l,r}\gets 1\)。
因为 \(st\) 可以低于 \(\mathcal O(n^3)\) 预处理，这个算法瓶颈在于 ASB 的转移。我们考虑如何优化：
首先枚举第一个断点也就是 A 的右端点 \(i\)，这个时候我们发现第二个断点（B 的左端点）仅有可能在 \(i+1\sim r_{i+1}+1\) 中取，其中 \(r_i\) 表示 \(i\) 往右最远的点满足 \([i,r_i]\) 中的字符全都是 * 或 ?。
那么可以考虑对 \(dp1\) 做前缀和：设 \(\displaystyle sum_{l,r}=\sum_{i=1}^l dp1_{i,r}\)，这样 ASB 转移方程就变成了：
\(\displaystyle dp2_{l,r}\gets dp2_{l,r}+\sum_{i=l}^{r-1}dp2_{l,i}\times(sum_{\min(r_{i+1}+1,r),r}-sum_{i,r})\)
复杂度 \(\mathcal O(n)\)，最后的复杂度 \(\mathcal O(n^3)\)。
代码
#include <bits/stdc++.h>
#define LL long long
#define sl(s) strlen(s)
#define endline puts("")
#define pii pair<int , int>
#define pr_q priority_queue
#define DEBUG puts("DEBUG.")
using namespace std;
const int N = 5e2 + 10;
const int inf = ~0u >> 2;
const int p = 1e9 + 7;
int n,k,dp1[N][N],dp2[N][N]; // independent, dependent
int sum[N][N],r[N];
bool st[N][N]; // all '*' or '?'
char s[N];
int main()
{
// freopen("bracket.in" , "r" , stdin);
// freopen("bracket.out" , "w" , stdout);
cin >> n >> k;
scanf("%s" , s + 1);
for(int i = 1;i <= n;i++)
{
for(int j = i;j <= n;j++)
{
bool flag = 0;
for(int c = i;c <= j;c++)
if(s[c] != '*' && s[c] != '?')
{
flag = 1;
break;
}
st[i][j] = !flag;
}
r[i] = i - 1;
for(int j = i;j <= min(n , i + k - 1);j++)
if(s[j] == '*' || s[j] == '?')
r[i] = j;
else
break;
}
for(int i = 1;i <= n;i++)
for(int j = 1;j <= i - 1;j++)
st[i][j] = 1;
for(int len = 2;len <= k + 2;len++)
for(int i = 1;i + len - 1 <= n;i++)
{
int j = i + len - 1;
bool flag = !st[i + 1][j - 1] || s[i] == '*' || s[i] == ')' || s[j] == '*' || s[j] == '(';
dp1[i][j] = dp2[i][j] = !flag;
if(len < 4)
for(int c = i;c <= j;c++)
sum[c][j] = ( sum[c][j] + dp1[i][j] ) % p;
// cout << flag << endl;
// cout << j << " " << j + i + 1 << " " << dp1[j][j + i + 1] << " " << dp2[j][j + i + 1] << endl;
}
for(int len = 4;len <= n;len++)
for(int i = 1;i + len - 1 <= n;i++)
{
int j = i + len - 1;
if(s[i] == '*' || s[j] == '*')
continue;
for(int c = i;c <= j - 2;c++)
if(r[c + 1] + 1 > j)
dp2[i][j] = (dp2[i][j] + 1ll * dp2[i][c] * (sum[j][j] - sum[c][j] + p) % p) % p;
else
dp2[i][j] = (dp2[i][j] + 1ll * dp2[i][c] * (sum[r[c + 1] + 1][j] - sum[c][j] + p) % p) % p;
// if( st[c + 1][c + d] )
// dp2[i][j] = (dp2[i][j] + 1ll * dp2[i][c] * dp1[c + d + 1][j] % p) % p;
if( (s[i] == '(' || s[i] == '?') && (s[j] == ')' || s[j] == '?') )
{
dp1[i][j] = ( dp2[i + 1][j - 1] + dp1[i][j] ) % p,dp2[i][j] = ( dp2[i + 1][j - 1] + dp2[i][j] ) % p;
for(int c = 1;c <= min(k , len - 3);c++)
{
if( st[j - c][j - 1] )
dp1[i][j] = ( dp1[i][j] + dp2[i + 1][j - 1 - c] ) % p,
dp2[i][j] = ( dp2[i][j] + dp2[i + 1][j - 1 - c] ) % p;
if( st[i + 1][i + c] )
dp1[i][j] = ( dp1[i][j] + dp2[i + c + 1][j - 1] ) % p,
dp2[i][j] = ( dp2[i][j] + dp2[i + c + 1][j - 1] ) % p;
}
}
sum[i][j] = ( sum[i - 1][j] + dp1[i][j] ) % p;
// cout << i << " " << j << " " << dp1[i][j] << " " << dp2[i][j] << endl;
}
cout << dp2[1][n] << endl;
return 0;
}
/*
10 2
???(*??(?)
*/