考场上想了 114514 年都没想出怎么直接不算重,然后写了个容斥减掉算重的调了 1919810 年还没调出来(貌似这样做不行?)/kk
看到 \(n\le 500\) 一眼区间 dp。
设 \(f_{i,j}\) 表示区间 \([i,j]\) 成为合法括号序列的答案。转移的话直接按照题目的方式转移就是了。
但是很明显像 ()()()
这样的序列会算重。。。
于是考虑对于 AB
、ASB
这样的转移,强制让它只从 \([i,\) 第一个左括号匹配的右括号的位置 \(]\) 转移过来。
可以考虑设 \(g_{i,j}\) 表示区间 \([i,j]\) 只由 ()
、(S)
、(A)
、(SA)
、(AS)
转移过来的合法序列个数。
这样就解决会算重的问题了。
实现时务必注意细节。
#include <bits/stdc++.h>
#define DEBUG fprintf(stderr, "Passing [%s] line %d\n", __FUNCTION__, __LINE__)
#define File(x) freopen(x".in","r",stdin); freopen(x".out","w",stdout)
#define DC int T = gi <int> (); while (T--)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long LL;
typedef pair <int, int> PII;
typedef pair <int, PII> PIII;
template <typename T>
inline T gi()
{
T f = 1, x = 0; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return f * x;
}
const int INF = 0x3f3f3f3f, N = 503, M = N << 1, mod = 1000000007;
int n, K;
int f[N][N], g[N][N], sum[N][N];
char s[N];
bool p[N][N];
int mn[N];
inline bool Can(int pos, char c) {return s[pos] == c || s[pos] == '?';}
inline void Add(int &x, int y) {x = (x + y) % mod;}
int main()
{
//File("");
n = gi <int> (), K = gi <int> ();
scanf("%s", s + 1);
memset(mn, 0x3f, sizeof mn);
for (int i = 1; i <= n; i+=1)
for (int j = i; j <= min(i + K - 1, n); j+=1)
if (Can(j, '*')) p[i][j] = true, mn[j] = min(mn[j], i);
else break;
for (int len = 2; len <= n; len+=1)
for (int i = 1; i + len - 1 <= n; i+=1)
{
int j = i + len - 1;
sum[i][j] = sum[i][j - 1];
if (!Can(i, '(') || !Can(j, ')')) continue;
if (len == 2) {f[i][j] = g[i][j] = 1; Add(sum[i][j], f[i][j]); continue;}
if (p[i + 1][j - 1]) f[i][j] = g[i][j] = 1;
for (int k = i; k < j; k+=1)
Add(g[i][j], 1ll * f[i][k] * g[k + 1][j] % mod);
for (int l = i + 1; l < j; l+=1)
if (mn[l] != 0x3f3f3f3f)
{
int tmp = max(mn[l], i + 1);
Add(g[i][j],
1ll * g[l + 1][j] *
((sum[i][l - 1] + mod - sum[i][tmp - 2]) % mod) % mod);
}
Add(f[i][j], g[i + 1][j - 1]), Add(g[i][j], g[i + 1][j - 1]);
for (int k = i + 1; k <= min(i + K, j - 2); k+=1)
if (p[i + 1][k])
Add(f[i][j], g[k + 1][j - 1]), Add(g[i][j], g[k + 1][j - 1]);
else break;
for (int k = max(i + 2, j - K); k < j; k+=1)
if (p[k][j - 1])
Add(f[i][j], g[i + 1][k - 1]), Add(g[i][j], g[i + 1][k - 1]);
Add(sum[i][j], f[i][j]);
}
printf("%d\n", g[1][n]);
return 0;
}