P8745 题解

· · 题解

P8745 括号序列

思路

这题关键点在于——什么是本质不同的添加结果。

首先注意，对于一个未匹配的括号序列 ())(()(()，删掉所有已经配对的括号，一定会得到 )(( 这样的序列。左边全是右括号，右边全是左括号。因此我们需要在左侧适当添加左括号，右侧添加右括号，才能使其合法。

接下来先着重关注左半边的情况。

不妨这么想：把合法的括号序列按照右括号 ) 分隔开，形成几个子串。每个字串都只包含若干个左括号 (。例如

()()() 拆分成 ( ( (

()(()) 拆分成 ( ((  

(())() 拆分成 ((   (

(()()) 拆分成 (( (  

((())) 拆分成 (((    

因此本质不同意味着划分方式不同，而我们求的其实是合法的划分方式。

因此，对于一个未匹配的括号序列 ()))，我们尝试在每两个右括号 ) 之间加入若干左括号 (，使其合法。

具体地，设 dp[i][j] 表示在第 i 个右括号之前，总共新加了 j 个左括号。同时为了保证合法，规定 num[i]\le j\le cnt 。其中 num[i] 表示 i 及其之前未匹配的右括号总数，故 j 至少大于等于 num[i]；cnt 表示整个串内的右括号数，比 cnt 还大的 j 必然是没有意义的，只会浪费复杂度。

转移枚举上一个右括号之前新加了多少左括号：

dp[i][j]=\sum_{k=num[i-1]}^{j} dp[i-1][k]

复杂度 \mathcal{O(n^3)}：

for(int i=1;i<=cnt;i++)
{
    for(int j=num[i];j<=cnt;j++)
    {
        for(int k=num[i-1];k<=j;k++)
        {
            dp[i][j]+=dp[i-1][k];
            dp[i][j]%=Mod;
        }
    }
}

优化很简单，对每个 i 做一次前缀和即可。达到 \mathcal{O(n^3)}。

对于右半边，只需要把整个串前后翻转，做一次镜像，再做一遍就行。

然后把两半边的方案数乘起来得到总方案数。

代码

//
//  main.cpp
//  P8745
//
//  Created by Leo Xia on 2023/11/9.
//

#include <bits/stdc++.h>
typedef long long ll;
const int N=5010,Mod=1000000007;
using namespace std;
string s;
ll dp[N][N];
int num[N],cnt;
ll L,R;
ll solve()
{
    int lcnt,rcnt;
    lcnt=rcnt=0;
    memset(num,0,sizeof(num));
    memset(dp,0,sizeof(dp));
    cnt=0;
    for(int i=0;i<s.length();i++)
    {
        if(s[i]=='(')lcnt++;
        else
        {
            rcnt++;
            if(lcnt){rcnt--;lcnt--;}
            num[++cnt]=rcnt;
        }
    }
    dp[0][0]=1;
    for(int i=1;i<=cnt;i++)
    {
        for(int j=num[i-1];j<=cnt;j++)
        {
            dp[i-1][j]+=dp[i-1][j-1];
            dp[i-1][j]%=Mod;
        }
        for(int j=num[i];j<=cnt;j++)
        {
            dp[i][j]+=(dp[i-1][j]-dp[i-1][num[i-1]-1])%Mod+Mod;
            dp[i][j]%=Mod;
        }
    }
    return dp[cnt][num[cnt]];
}
void rev()
{
    string tmp;
    tmp.clear();
    for(int i=s.length()-1;i>=0;i--)
        tmp.push_back(s[i]=='('?')':'(');
    s=tmp;
}
int main()
{
    //freopen
    ios::sync_with_stdio(0);
    cin>>s;
    L=solve()%Mod;
    rev();
    R=solve()%Mod;
    cout<<L*R%Mod;
    return 0;
}