| 12345 |
- #include <iostream>
- #include <string>
- #include <vector>
- using namespace std;constexpr long long MOD=1000000007;
- int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n,K;string s;cin>>n>>K>>s;vector<vector<char>>star(n,vector<char>(n));for(int l=0;l<n;++l){bool ok=true;for(int r=l;r<n&&r-l+1<=K;++r){ok&=s[r]=='*'||s[r]=='?';star[l][r]=ok;}}vector<vector<long long>>valid(n,vector<long long>(n)),primitive(n,vector<long long>(n)),after(n,vector<long long>(n));auto left_ok=[&](int i){return s[i]=='('||s[i]=='?';};auto right_ok=[&](int i){return s[i]==')'||s[i]=='?';};for(int len=2;len<=n;++len)for(int l=0;l+len<=n;++l){int r=l+len-1;if(left_ok(l)&&right_ok(r)){long long ways=len==2;if(len>2){int a=l+1,b=r-1;ways=(valid[a][b]+star[a][b])%MOD;for(int mid=a;mid<b;++mid){if(star[mid+1][b])ways=(ways+valid[a][mid])%MOD;if(star[a][mid])ways=(ways+valid[mid+1][b])%MOD;}}primitive[l][r]=ways;}long long ways=primitive[l][r];for(int mid=l;mid<r;++mid)ways=(ways+primitive[l][mid]*after[mid+1][r])%MOD;valid[l][r]=ways;ways=valid[l][r];for(int mid=l;mid<r&&mid-l+1<=K;++mid)if(star[l][mid])ways=(ways+valid[mid+1][r])%MOD;after[l][r]=ways;}cout<<valid[0][n-1]<<'\n';}
|
