zcmimi's blog
avatar
zc
2020-09-10 12:45:00
  • 本文总阅读量
查看原题

点击跳转

每个容器x求出它存活轮数的期望可以表示为

\sum_{i=1}^{n-1}P(x_i)

x_i表示第x个容器到第i轮仍未被击倒

记录L_ii左边第一个比它大的数的位置,R_ii右边第一个比它大的数的位置

每个容器i被击倒的时候也就是[L_i,i][i,R_i]的容器都被选中

P(A)表示[L_i,i]全被选中,P(B)表示[i,R_i]全部被选中,l=i-L_i,r=R_i-i,

\displaystyle \begin{aligned} P(x_i) &=1-P(A)-P(B)+P(AB)\\ &=1-\frac{{n-1-l \choose i-l}-{n-1-r\choose i-r}+{n-1-l-r\choose i-l-r}}{n-1\choose i} \end{aligned}

#include<bits/stdc++.h>
const int N=55,P=998244353;
int n,a[N],L[N],R[N],q[N],tp,C[N][N];
int pw(int x,int b){
    int res=1;
    while(b){
        if(b&1)res=1ll*res*x%P;
        b>>=1,x=1ll*x*x%P;
    }
    return res;
}
int inv(int x){return pw(x,P-2);}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",a+i);
        while(tp&&a[i]>a[q[tp]])R[q[tp--]]=i;
        L[i]=q[tp];q[++tp]=i;
    }
    C[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])%P;
    }
    for(int x=1;x<=n;++x){
        int res=0,l=x-L[x],r=R[x]-x;
        if(!L[x])l=0;if(!R[x])r=0;
        long long ce;
        for(int i=1;i<n;++i){
            ce=
                (l?C[n-1-l][i-l]:0)+
                (r?C[n-1-r][i-r]:0)-
                (l&&r&&i-l-r>=0?C[n-1-l-r][i-l-r]:0);
            ce=1ll*(ce%P+P)%P*inv(C[n-1][i])%P;
            res=(res+1-ce+P)%P;
        }
        printf("%d ",res);
    }
}
LG 6046 纯粹容器
comment评论
Search
search