移言丁真：Unavoided linyue 题解

· · 题解

这种题当然要把括号序转化成格路啦！（如果你没见过这个操作，建议换道题做）

将左括号视为向上走，右括号视为向下走，那么容易发现：

最终括号串的权值只和它的 h_1+h_2 有关，我们相当于要最大化最后长串的 h_1+h_2。如果我们已知了所有括号串的 h_1 和 h_2，那么假如已知某个串作为了最低点所在的串，其他串里 h_1 \le h_2 的都应该放到这个串右边，否则就放到这个串左边，它们对答案的贡献都是 |h_1-h_2|，而那个作为最低点的串对答案的贡献是 h_1+h_2＝|h_1-h_2|+2\min(h_1,h_2)。因此，如果选 \min(h_1,h_2) 最大的串作为最低点所在的串，不仅可以最大化答案，并且还一定可以成功让其处于最低点！

所以说，我们想求出长串 h_1+h_2 的最大值的期望，只需先求出每个串 |h_1-h_2| 的期望，再对于每个自然数 k 求出最后各串 \min(h_1,h_2) 的最大值为 k 的概率即可。可以改为求最大值不大于 k 的概率，然后作差分。这样的话只要对于每个串求出它的 \min(h_1,h_2) 不大于 k 的概率再乘起来，而这个又可以被写成 1-P(h_1,h_2＞k)。

现在我们只要对于每个串快速求出它的 h_1,h_2 均大于 k 的概率。考虑枚举第一个最低点，那么向两边走时需要满足的限制为“不能比起点低，终点要比某坐标高”，而这样的方案数其实和“没有特殊限制，终点坐标为一定值”一样，这样问题就被转化为了“固定起点终点，求路径与某直线相交次数和”，你可以用喜欢的方法推出答案为组合数前缀和，然后递推就可以实现 O(n)，这题做完啦！

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cassert>
#define mod 1000000007
#define inv2 500000004
#define int long long
#define add(a,b) (a+=(b),a>=mod?a-=mod:0)
#define neg(x) ((x)&1?mod-1:1)
#define Q(a,b) C((a)+(b)-1,(b)-1)
using namespace std;
int fac[4007693],ifac[4007693];
int C(int n1,int m1){
    if(m1<0||m1>n1)return 0;
    return fac[n1]*ifac[m1]%mod*ifac[n1-m1]%mod;
}
inline int qpow(int n1,int n2){
    int n3=n1,n4=1;
    while(n2){
        if(n2&1)n4*=n3,n4%=mod;
        n3*=n3,n3%=mod;n2>>=1;
    }return n4;
}
inline int mut(initializer_list<int> arg){
    int ret=1;
    for(auto i:arg)ret*=i,ret%=mod;
    return ret;
}
int m,n,l[4076930],cnt,ans,ca[4076930],ck[4076930],r[4076930];     
signed main(){
    fac[0]=1;for(int i=1;i<=4001010;i++)fac[i]=fac[i-1]*i%mod;
    ifac[4001010]=qpow(fac[4001010],mod-2);for(int i=4001010;i>=1;i--)ifac[i-1]=ifac[i]*i%mod;
    scanf("%lld",&m);
    for(int i=1;i<=m;i++)scanf("%lld",l+i),n+=l[i],r[l[i]]++;
    for(int i=0;i<=n;i++)ca[i]=1;
    for(int i=1;i<=n;i++){
        if(r[i]==0)continue;
        ck[0]=1;for(int j=1;j+j<=i;j++)ck[j]=(ck[j-1]+C(i,j))%mod;
//        for(int j=0;j+j<=i;j++)printf("%lld ",ck[j]);printf("\n");
        int p2=qpow(2,i),ip2=qpow(p2,mod-2);
        for(int j=0;j+j<=i;j++){
            if(i&1)ca[j]=ca[j]*qpow((p2-2*(i/2-1>=j?ck[i/2-j-1]:0)+2*mod)%mod*ip2%mod,r[i])%mod;
            else ca[j]=ca[j]*qpow((p2-(i/2-1>=j?ck[i/2-j-1]:0)-(i/2-2>=j?ck[i/2-j-2]:0)+2*mod)%mod*ip2%mod,r[i])%mod;
        }
    }
//   for(int i=0;i<=n;i++)printf("%lld ",ca[i]*qpow(2,n)%mod);printf("\n");
    for(int i=n;i>=1;i--)add(ca[i],mod-ca[i-1]);
//  for(int i=0;i<=n;i++)printf("%lld ",ca[i]*qpow(2,n)%mod);printf("\n");
    for(int i=1;i<=n;i++)ans=(ans+ca[i]*i*2)%mod;
//    printf("%lld\n",ans*qpow(2,n)%mod);
    for(int i=1;i<=n;i++){
        if(r[i]==0)continue;
        int cur=0;for(int j=0;j<=i;j++)cur+=max(i-j*2,j*2-i)*C(i,j)%mod;
        ans=(ans+mut({r[i],cur%mod,qpow(inv2,i)}))%mod;
    }
//  printf("%lld\n",ans*qpow(2,n)%mod);
    ans=(n-ans+mod)*inv2%mod;
//    printf("%lld\n",ans*qpow(2,n)%mod);
    printf("%lld",ans);
}

"相关链接"