CF785D Anton and School - 2 题解

分析

很明显有一种 \(\mathcal O(n^2)\) 的做法，遍历每一个 (，再枚举 \(k\)，左边不包含这一位选 \(k-1\) 个 (，右边选 \(k\) 个 )，求组和即可。

但是数据范围是 \(n \le 2\times 10^5\)。

假设 \(a_i\) 表示第 \(i\) 位前有几个左括号，\(b_i\) 表示第 \(i\) 位后有几个右括号，可将 \(n^2\) 做法的式子列出来：

\[\sum \limits_k \binom{a_i-1}{k-1}\binom{b_i}{k} \]

根据范德蒙德卷积（如下）

\[\sum \limits_{i=0}^{k} \binom{n}{i}\binom{m}{k-i}=\binom{n+m}{k} \]

可将原式变形为：

\[\sum \limits_k \binom{a_i-1}{a_i-k}\binom{b_i}{k}=\binom{a_i+b_i-1}{a_i} \]

将组合数预处理出来就行。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
namespace Raiden
{
    const int mod=1e9+7;
    const int N=2e5+5;
    int mut[N],inv[N];
    int a[N],b[N];
    int qpow(int a,int b)
    {
        int res=1;
        for(;b;b>>=1)
        {
            if(b&1)res=res*a%mod;
            a=a*a%mod;
        }
        return res%mod;
    }
    void _init()
    {
        mut[0]=1;
        for(int i=1;i<=N;i++)
            mut[i]=mut[i-1]*i%mod;
        inv[N]=qpow(mut[N],mod-2);
        for(int i=N-1;i>=0;i--)
            inv[i]=inv[i+1]*(i+1)%mod;
    }
    int get_C(int n,int m)
    {
        if(n<m||n<0||m<0)return 0;
        return 1ll*mut[n]*inv[m]%mod*inv[n-m]%mod;
    }
    signed work()
    {
        _init();
        string s;
        cin>>s;
        for(int i=0;i<s.size();i++)
            a[i]=a[i-1]+(s[i]=='(');
        for(int i=s.size()-1;i>=0;i--)
            b[i]=b[i+1]+(s[i]==')');
        int ans=0;
        for(int i=0;i<s.size();i++)
            if(s[i]=='(')
                ans=(ans+get_C(a[i]+b[i]-1,a[i]))%mod;
        cout<<ans<<endl;
        return 0;
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return Raiden::work();
}