题解 P7044 【「MCOI-03」括号】

· · 题解

一个括号串的 0 级偏值就是进行括号匹配后还未匹配的左括号和右括号数之和（因为中间括号尽可能配对一定是最优的）。

设子串 S(l,r) 未匹配的左括号和右括号数之和为 f(l,r)。

利用组合数知识可知答案为：

\begin{aligned}&\sum\limits_{1\leqslant l\leqslant r\leqslant n}^n\dbinom{l+k-2}{k-1}\dbinom{n-r+k-1}{k-1}f(l,r)\\=&\sum\limits_{l=1}^n\dbinom{l+k-2}{k-1}\sum\limits_{r=l}^n\dbinom{n-r+k-1}{k-1}f(l,r)\end{aligned}

直接枚举 l，根据当前括号在 S 中的匹配状况维护 \sum\limits_{r=l}^n\dbinom{n-r+k-1}{k-1}f(l,r) 即可。

利用后缀和可以做到 O(n)。

#include<bits/stdc++.h>
using namespace std;
#define p 998244353
#define N 2000000
int jc[N+5],ny[N+5];
int c[1000005],r[1000005];
int z[1000005],zd,rp[1000005],l;
int n,k,ans,lans;
int C(int x,int y){return 1ll*jc[x]*ny[y]%p*ny[x-y]%p;}
int main()
{
    jc[0]=ny[0]=ny[1]=1;
    for(int i=1;i<=N;i++)jc[i]=1ll*i*jc[i-1]%p;
    for(int i=2;i<=N;i++)ny[i]=1ll*(p-p/i)*ny[p%i]%p;
    for(int i=1;i<=N;i++)ny[i]=1ll*ny[i]*ny[i-1]%p;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        char ch=getchar();
        while(ch!='('&&ch!=')')ch=getchar();
        c[i]=ch=='('?1:0;
    }
    for(int i=1;i<=n;i++)r[i]=C(n-i+k-1,k-1);
    for(int i=1;i<=n;i++)
    {
        if(c[i])z[++zd]=i;
        else if(zd)rp[z[zd--]]=i;
        else ++l;
        lans=(lans+1ll*r[i]*(zd+l))%p;
    }
    for(int i=n;i;i--)r[i]=(r[i]+r[i+1])%p;
    for(int i=1;i<=n;i++)
    {
        ans=(ans+1ll*C(i+k-2,k-1)*lans)%p,lans=(lans-r[i]+p)%p;
        if(rp[i])lans=(lans+1ll*2*r[rp[i]])%p;
    }
    printf("%d",ans);
}