自动搬运

查看原文

来自洛谷，原作者为

	Anoshag_Ruwan AFO|庭迹一如故

搬运于2025-08-24 23:02:17，当前版本为作者最后更新于2024-08-23 21:57:33，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这道题的核心在于括号序列向格路计数的转化以及找 $h_1+h_2$ 的思路，主要想（保姆级）补充一下 linyue 官方题解中的数学推导部分。

首先，答案与 $h_1+h_2$ 的关系是 $ans=\frac{n-h_1-h_2}{2}$，这个易得，删去括号串中最左侧的 $h_1$ 个右括号与最右侧的 $h_2$ 个左括号，总能得到一个合法的括号匹配序列。关键在于求所有串 $|h_1-h_2|$ 以及 $\max(\min(h_1,h_2))$ 的期望。

首先有结论，从 $(0,h_1)$ 以格路走到 $(n,h_2)(h_1,h_2\ge 0)$，要求中间不穿过 $x$ 轴的路线数为 $g(n,h_1,h_2)=(\tbinom{n}{\frac{n-h_1+h_2}{2}}-\tbinom{n}{\frac{n+h_1+h_2+2}{2}})[h_1+h_2\equiv n\bmod2]$。这是计数的常见套路，假设另一个人从 $(0,-2-h_1)$ 走到同样的终点，将其从起点到第一次经过 $y=-1$ 的路径轴对称到上方，则每个从 $(0,h_1)$ 到 $(n,h_2)$ 的不合法路径与起点关于 $y=-1$ 轴对称的任意路径便建立了一一对应。若限定 $h_1$ 与 $h_2$ 的值也可直接差分就行。

对于第一部分即求 $E(k,|h_1-h_2|)$（$k$ 为字符串长度），这个不需要上述结论，考虑让路径长度 $+1$ 的过程，末尾可以添加向上或向下一步，若 $h_1\ne h_2$，则答案有均等概率 $+1$ 或 $-1$，仅有 $h_1=h_2$ 时无论如何只会导致答案 $+1$，因此 $E(|h_1-h_2|)$ 的增量就等于 $h_1=h_2$ 的方案数，前缀和得 $E(k,|h_1-h_2|)=\sum\limits_{i=0}^{\lfloor\frac{k+1}{2}\rfloor}\tbinom{2i}{i}\frac{1}{4^i}$，$O(n)$ 递推处理即可。

对于第二部分 $E(\max)$ 就不能相互独立来求了，先一步转化 $E(\max(h))=\sum\limits_{k\ge 1}P(\max(h)\ge k)=\sum\limits_{k\ge 0}(1-P(\forall a_i,\min(h_1,h_2)\le k))$，对于每个 $k$ 就满足 $a_i$ 相互独立了。为避免容斥再启动第一部分的递推，当且仅当 $h_1> k,h_2=k$ 或 $k+1$ 时，末尾添加一步可以产生概率的贡献。因此 $P(n,\min\le k)=1+\frac{1}{2}\sum\limits_{m\le 1}^{n-1}(P(m,h_1>k,h_2=k+1)-P(m,h_1>k,h_2=k))$。

应用一开始的结论，$P(m,h_1>k,h_2=k)=2^{-m}(\sum\limits_{ k_1>k}g(m,k_1,k)-g(m,k_1-1,k-1))$，$\sum\limits_{k_1>k}g(m,k_1,k)=\sum\limits{\tbinom{n}{\frac{n-k_1+k}{2}}-\tbinom{m}{\frac{m-k_1-k-2}{2}}}=\sum\limits_{i=1}^{2k+1}\tbinom{m}{\frac{m-i}{2}}$，因此 $P(m,h_1>k,h_2=k)=2^{-m}\tbinom{m}{\lfloor\frac{m-2k-1}{2}\rfloor}$，同理 $P(m,h_1>k,h_2=k+1)=2^{-m}\tbinom{m}{\lfloor\frac{m-2k-2}{2}\rfloor}$，而当 $m$ 为偶数时，对概率的贡献严格为 $0$，$P(n,\min\le k)=\sum\limits_{i=0}^{\lfloor\frac{k-1}{2}\rfloor}2^{-1-2i}(\tbinom{2i+1}{i-k}-\tbinom{2i+1}{i-k-1})$，设 $n_0=n+1+(n\bmod 2)$，由杨辉三角结论可得 $P(n,\min\le k)=2^{n_0+1}\sum\limits_{i=0}^k\tbinom{n_0}{\frac{n_0-1}{2}-i}$，十分优美的形式。

然后现在到代码实现环节，你发现数据范围是关于 $\sum{a_i}$ 线性的，开 $a_i$ 个指针在杨辉三角对应行上移动即可，时间复杂度 $O(n+m)$，代码十分简洁。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define LL long long
using namespace std;
const int p=1e9+7,N=4e6+11,iv=5e8+4;
LL a[N],b[N],c1[N],c2[N],frc[N],inv[N];
inline LL add(LL x,LL y){return x+y>=p?x+y-p:x+y;}
inline LL cmb(LL x,LL y){return x<y||y<0?0:frc[x]*inv[y]%p*inv[x-y]%p;}
inline LL ksm(LL x,LL y){
	LL k=1,l=x;
	while(y){if(y&1)k=k*l%p;l=l*l%p,y>>=1;}
	return k;}
inline LL rd(){
	LL i=0,j=1;char g=getchar();
	while(g>57||g<48){if(g=='-')j=-1;g=getchar();}
	while(g>47&&g<58)i=(i<<3)+(i<<1)+g-48,g=getchar();
	return i*j;
}
int main()
{
	LL i,j,h,k,m=0,n=rd(),ans=0,as=0;
	for(i=1;i<=n;i++)a[i]=rd(),m=add(m,a[i]);sort(a+1,a+n+1);
	for(i=frc[0]=b[0]=1;i<=m;i++)frc[i]=frc[i-1]*i%p,b[i]=b[i-1]*iv%p;
	for(i=m,inv[m]=ksm(frc[m],p-2);i;i--)inv[i-1]=inv[i]*i%p;
	for(i=2;i<=m+1;i+=2)c1[i]=c1[i-1]=add(c1[i-2],cmb(i-2,i-2>>1)*b[i-2]%p);
	for(i=1;i<=n;i++)ans=add(ans,c1[a[i]]),a[i]>>=1;
	for(i=0,j=1;i<a[n];i++){
		for(k=1,h=j;h<=n;h++)c2[h]=add(c2[h],cmb((a[h]<<1)+1,a[h]-i)*b[a[h]<<1]%p),k=k*c2[h]%p;
		while(a[j]<=i)j++;as=add(as+1,p-k);
	}ans=add(m,p-add(ans,add(as,as)))*iv%p;
	printf("%lld\n",ans);
	return 0;
}