题解 | #牛牛学括号#

这里用回溯的话肯定炸了，我们观察会发现，实际上对于这种括号问题，每一个左边括号的所有匹配方案是由他右边的右括号决定的，有多少右括号就有多少种选择方式，我们就可以很简单的直接从右往左扫一遍，遇见了左括号就从已有的右括号里拿出一个（都可以配对），然后后续的再次配对由于顺序天然的避免了不可能的情况（也就是都可以拿到）所以说乘就可以了 由于一开始的字符串是肯定的所以说ans至少有一种情况

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

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    string s;
    
    int MOD = 1e9 + 7;
    
    cin>>s;
    
    int ans = 1;
    //题目说过了至少合规
    
    int n = s.size();
    
    int rnum = 0;
    
    for(int r = n - 1;r >= 0;r--)
    {
        if(s[r] == ')')
        {
            rnum++;
        }
        else
        {
            ans *= rnum;
            
            ans = ans % MOD;
            
            rnum--;
        }
    }
    
    cout<<ans<<'\n';
    
    return 0;
}