CF1264D Beautiful Bracket Sequence

$\color{deeppink}link1$ $\color{deeppink}link2$

长度为 $n$ 的字符串，其中只有 (, ), ?三种字符，其中 ? 可以替换为 ( 或者 )。

定义一个字符串的权值为通过删除某些字符后可以达到形态类似于 ((...+...)) 的最大的左括号个数。

其中 D1 $n\le2000$，D2 $n\le 10^6$。

通过观察，其实可以发现有一个位置 $i$ 是一定可以作为中间分割左右括号的点，那就是当 $i$ 左边的左括号个数等于右边的右括号个数时。

这十分显然，而且若这样算是不重不漏的，因为在一个确定的字符串中只有一个点，他的左右两边左右括号个数相同，过了这个点后左括号会增加，右括号会减少，自然不相同了。

那么可以跑一个暴力 DP，可以过 D1。

将 D1 的 DP 式转为组合数的形式，实际上就是

$\sum_{i=0}^x (l+i)\binom xi\binom y{l+i-r}$

其中 $i$ 是枚举左边有多少个问号变为左括号，$l$ 是左边左括号个数，$r$ 是右边右括号个数，$x$ 是左边问号个数，$y$ 是右边问号个数。

继续化简

$\begin{aligned} \sum_{i=0}^x (l+i)\binom xi\binom y{l+i-r} &=l\sum_{i=0}^x \binom xi\binom y{l+i-r}+\sum_{i=0}^x i\binom xi\binom y{l+i-r} \end{aligned}$

对于左边的式子，有

$l\sum_{i=0}^x \binom xi\binom y{l+i-r} =l\sum_{i=0}^x \binom xi\binom y{y-l+r-i}$

警钟敲烂：还有一个范德蒙恒等式，就是 $\sum_{i=0}\binom{n}{i}\binom m {k-i}=\binom {n+m}k$。

具体证明如下：

$\begin{aligned} (1+x)^{n+m} &=\sum_{i=0}^{n+m}\binom {n+m}ix^i\\ &=(1+x)^n(1+x)^m\\ &=\sum_{i=0}^n\binom nix_i\times \sum_{j=0}^m\binom mjx^j\\ &=\sum_{i=0}^{n+m}\sum_{j=0}^i\binom nj\binom m{i-j}x^i\\ \end{aligned}$

然后看 $x^i$ 的系数即可。

于是上式可化为 $l\dbinom {x+y}{y-l+r}$。

右边的式子稍作改动，变为

$\sum_{i=0}^xx\binom {x-1}{i-1}\binom y{y-l+r-1-(i-1)}$

那么可化为 $x\dbinom {x+y-1}{y-l+r-1}$。

将两个式子加起来即可线性求出答案。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=4e6+50,mod=998244353;

int n,fir[N],pre[N],num[N],ans,cm[N];
char a[N];

int ksm(int a,int b)
{
	int ans=1;
	while(b)
	{
		if(b&1)ans=ans*a%mod;
		a=a*a%mod;b>>=1;
	}
	return ans;
}

int inv(int x){return ksm(x,mod-2);}

int C(int n,int m)
{
	if(n<m||n<0||m<0)return 0;
	return cm[n]*inv(cm[n-m]*cm[m]%mod)%mod;
}

main()
{
	cin>>(a+1);n=strlen(a+1);
	cm[0]=1;
	for(int i=1;i<=n;i++)cm[i]=cm[i-1]*i%mod;
	for(int i=1;i<=n;i++)
	{
		fir[i]=fir[i-1];fir[i]+=(a[i]=='(');
		num[i]=num[i-1];num[i]+=(a[i]=='?');
		pre[i]=pre[i-1];pre[i]+=(a[i]==')');
	}
	for(int i=1;i<=n;i++)
	{
		int l=fir[i],r=pre[n]-pre[i],x=num[i],y=num[n]-num[i];
		ans=(ans+
		l*C(x+y,y+r-l)%mod+x*C(x+y-1,y-l+r-1)%mod
		)%mod;
	}
	cout<<ans;
}