自动搬运

查看原文

来自洛谷，原作者为

	littleKtian MoVe yoUR BoDy

搬运于2025-08-24 22:26:09，当前版本为作者最后更新于2020-11-02 14:20:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

一个括号串的 $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);
}