P10896 【移言丁真：Unavoided linyue】题解

· · 题解

这道题的核心在于括号序列向格路计数的转化以及找 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;
}