S组T3

$O(N^3)$ TLE 65pts

#include <bits/stdc++.h>
#define N 510
#define ll long long
using namespace std;

string s;
ll n, k, ans, f[N], mod = 1e9+7, d1[N][N], d2[N][N], ss[N];

int main(){
	scanf("%lld%lld",&n,&k);
	cin >> s;
	for(int i = 0; i < s.size(); i++)
		f[i+1] = f[i] + (s[i] == '*' || s[i] == '?');
	for(ll l = 1; l + 1 <= s.size(); l++)
		if((s[l-1] == '(' || s[l-1] == '?') && (s[l] == ')' || s[l] == '?')) d1[l][l+1] = 1;
	for(ll i = 3; i <= s.size(); i++){
		for(ll l = 1; l + i - 1 <= s.size(); l++){
			ll r = l + i - 1;
			if((s[l-1] != '(' && s[l-1] != '?') || (s[r-1] != ')' && s[r-1] != '?')) d1[l][r] = 0;
			else{
				d1[l][r] = ((d1[l+1][r-1] + d2[l+1][r-1]) % mod + (f[r-1] - f[l] == r - l - 1 && r - l - 1 <= k)) % mod;
				for(int j = 1; j <= k; j++){
					if(f[l+j] - f[l] == j) d1[l][r] = (d1[l][r] + (d1[l+1+j][r-1] + d2[l+j+1][r-1])%mod)%mod;
					if(f[r-1] - f[r-j-1] == j) d1[l][r] = (d1[l][r] + (d1[l+1][r-j-1] + d2[l+1][r-j-1])%mod)%mod;
				}
			}
			if(l + 3 > r || (s[l-1] != '(' && s[l-1] != '?') || (s[r-1] != ')' && s[r-1] != '?')) d2[l][r] = 0;
			else{
				memset(ss,0,sizeof(ss));
				for(int j = r-1; j >= l+2; j--) ss[j] = (ss[j+1] + d1[j][r]) % mod;
				ll head = l + 2;
				for(int j = l + 2; j <= r; j++){
					if(j - 1 == head) head++;
					while(head < r && head - j < k && (s[head-1] == '*' || s[head-1] == '?')) head++;
					d2[l][r] = (d2[l][r] + (d1[l][j-1] + d2[l][j-1])%mod * (((ss[j] - ss[head+1])%mod+mod)%mod)%mod) % mod;
				}
			}
		}
	}
	printf("%lld\n",(d1[1][s.size()] + d2[1][s.size()])%mod);
	return 0;
}