CF785D题解

_masppy_ · 2023-11-14 19:27:28 · 题解

题目链接：Link

题目大意：

给定一个长度为 2n 的括号序列，求该序列能选出多少个完全匹配的子序列，同时保证该序列前半部分均为 '('，后半部分均为 ')'，答案对 1e9+7 取模。

解题思路：

考虑对于一个左括号（右括号同理），当它作为所选取的子序列中位置最靠右的左括号时，能够选取出的合法子序列个数，假设它左面有 x 个左括号，右面有 y 个右括号，则个数为 \sum\limits_{i=0}^{min(x,y-1)}{C_x^i \times C_y^{i+1}}。

如果直接按照这个式子求解的话时间复杂度肯定会炸，于是考虑如何简化。可以发现这个式子等价于 \sum\limits_{i=0}^{min(x,y-1)}{C_x^{x-i} \times C_y^{i+1}}，显然由于 i 在不断移动，且覆盖了 x 和 y 的所有选择情况，同时选择出的括号个数始终为 x+1，则这个式子显然也可以等价为 C_{x+y}^{x+1}。

于是考虑记录一个前缀左括号和和后缀右括号和，对于所有的左括号计算贡献并累加即可。

由于数据规模较大且需要取模，考虑预处理出所有数的阶乘与逆元，快速计算组合数。

代码如下：

ll calc(ll a,ll b){//计算组合数
    return mut[a]*((p[b]*p[a-b])%mod)%mod;
}

int main(){
    scanf("%s",c+1);

    pre[0]=0;
    n=strlen(c+1);

    mut[1]=1;
    p[1]=p[0]=1;
    for(int i=2ll;i<=n;i++){
        mut[i]=(mut[i-1]*i)%mod;//预处理阶乘与逆元
        p[i]=q_pow(mut[i],mod-2);//快速幂求逆元
    }

    for(int i=1;i<=n;i++){
        pre[i]=pre[i-1]+(c[i]=='(');//左括号计数
    }

    back[n+1]=0;
    for(int i=n;i>=1;i--){
        back[i]=back[i+1]+(c[i]==')');//右括号计数
    }

    ll sum=0;
    for(int i=1;i<=n;i++){//递推
        if(c[i]=='(') sum=(sum+calc(pre[i-1]+back[i],pre[i])%mod)%mod;
    }

    printf("%lld",sum);

    return 0;
}

完结撒花 OvO！！！