一道题

· · 题解

题目

其中 n\le 500。

分析

直接统计概率是不好做的，直接计算全部操作完合法括号串有多少个也不好做。因为操作包含两部分：选择位置与选择类型，选择类型的概率可以直接在 dp 中计算，而位置却不好计算，考虑 dp 进行后在除以总位置方案数 \prod_{i=1}^n(2i-1) 就是最终的概率。

一般的括号区间计数dp为设状态 dp_{l,r,0/1} 表示区间 [l,r]最后一次操作是外面套一层/两个串合并，合并时为了避免重复左边只有 dp_{l,mid,0} 做贡献。

回到此题，可以套路的将 ) 视为 +1，( 为 -1，合法的条件即为前缀和 max \le 0。 因此设状态 dp_{l,r,x,0/1}，x 为该区间的前缀和 max。

发现这样设计在状态合并时有很好的性质，因为最终的和为 0，那么两个串合并时，前缀和max即两个串的前缀和 max 取 max。

因此可列出转移方程式。

dp_{l,r,x,0}=p\times (dp_{l+1,r-1,x+1,0}+dp_{l+1,r-1,x+1,1})+(1-p)\times (dp_{l+1,r-1,max(x-1,0),0}+dp_{l+1,r-1,max(x-1,0),1})\\ \\ dp_{l,r,x,1}=dp_{l,mid,x,0}\times (dp_{mid+1,r,y,0}+dp_{mid+1,r,y,1})+dp_{l,mid,y,0}\times (dp_{mid+1,r,x,0}+dp_{mid+1,r,x,1})(y\ge x)

复杂度是 O(n^5)，发现二式能前缀和优化，可以降到 O(n^4)。

观察发现长度一样的串本质上是一致的，令 f_{i,j,0/1} 为长度为 2i，前缀和 max 为j,最后一次操作为 0/1 的概率。

可知 f_{i,j,0/1}=\sum\limits_{r-l+1=i} dp_{l,r,j,0/1}，且转移式与 dp 相同，于是求出 f_{n,0,0/1}，这道题就被解决了，复杂度 O(n^3)

代码

void Main(){
    n=rd;
    int x=rd,y=rd;
    p=x*qmi(y,mod-2)%mod;
    C[0][0]=dp[0][0][0]=1;
    for(int i=1;i<=n;i++){
        C[i][0]=1;
        for(int j=1;j<=i;j++)
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
    }
    for(int i=0;i<=n;i++)
        sum[0][i][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=n;j++){
            int x=0,y=0;
            for(int k=1;k<i;k++){
                x=sum[k][j][0]*((sum[i-k][j][1]+sum[i-k][j][0])%mod)%mod;
                if(j) y=sum[k][j-1][0]*((sum[i-k][j-1][1]+sum[i-k][j-1][0])%mod)%mod;
                //这里是前缀和优化
                else y=0;
                dp[i][j][1]=(dp[i][j][1]+(x-y+mod)%mod*C[i][k]%mod)%mod;
            }
            if(j){
                dp[i][j][0]=(dp[i][j][0]+(mod+1-p)%mod*((dp[i-1][j-1][0]+dp[i-1][j-1][1])%mod)%mod)%mod;
                dp[i][j][0]=(dp[i][j][0]+p*((dp[i-1][j+1][1]+dp[i-1][j+1][0])%mod)%mod)%mod;
                sum[i][j][0]=(sum[i][j-1][0]+dp[i][j][0])%mod;
                sum[i][j][1]=(sum[i][j-1][1]+dp[i][j][1])%mod;
            }
            else{
                dp[i][j][0]=(dp[i][j][0]+p*((dp[i-1][j+1][1]+dp[i-1][j+1][0])%mod)%mod)%mod;
                dp[i][j][0]=(dp[i][j][0]+p*((dp[i-1][j][1]+dp[i-1][j][0])%mod)%mod)%mod;
                sum[i][j][0]=dp[i][j][0];
                sum[i][j][1]=dp[i][j][1];
            }
        }
    }
    int ans=(dp[n][0][0]+dp[n][0][1])%mod;
    for(int i=1;i<=n;i++)
        ans=ans*qmi(2*i-1,mod-2)%mod;
    cout<<ans<<endl;
}

闲话

这道题赛时有个地方没取模导致挂成10pts（好像也不是）重构了一下就对了。 本题好像套个多项式有更低复杂度？？但是不会多项式。