• 白王正在挑选容器。

白王制造了 nn 个容器,并将它们排成了一队,从左到右依次编号为 1n1 \sim n。第 ii 个容器的强度为 aia_i,保证 aia_i 互不相同。为了挑选出最纯粹的容器,白王会进行 n1n-1 轮操作,每轮操作中,他会等概率随机挑选两个 位置相邻 且 未被击倒 的容器,令它们进行决斗,在一次决斗中,强度较小的容器将会被击倒并移出队列。

显然最后留下的是强度最大的容器,但是,可怜的容器们很想知道自己能够活多久,于是,它们请你对每个容器求出它存活轮数的期望。答案对 998244353998244353取模。

一个容器的存活轮数为最大的非负整数 x<nx < n 满足它在第 xx 轮未被击倒。

两个容器 iijj 位置相邻当且仅当不存在 kk 满足 i<k<ji<k<jkk 号容器未被击倒。

大致题意 📖

链接 🔗

P6046 纯粹容器

题解 ❓

g[i][j]g[i][j] 为第ii个容器前jj轮被击倒的概率,f[i][j]f[i][j] 为第ii个容器第jj轮被击倒的概率
显然f[i][j]=g[i][j]g[i][j1]f[i][j] = g[i][j] - g[i][j-1]
考虑求g[i][j]g[i][j]
设每个容器左边和右边第一个大于该容器的位置为l[i],r[i]l[i],r[i],当他们之间的容器都被选择时,该容器会被击败
因此我们可通过组合数,固定选择左边il[i]i-l[i]或右边r[i]ir[i] - i个容器,然后求出概率
当然选择左边和选择右边时会出现重复选择的情况,因此我们需要简单容斥一下
g[i][j]=clca(il[i],j)+clca(r[i]i,j)clca(r[i]l[i],j)g[i][j] = clca(i - l[i] ,j) + clca(r[i] - i, j) - clca(r[i] - l[i] , j)

clca(i,j)=Aji(n1i)!/(n1)!clca(i,j) = A_j^i \cdot (n−1−i)! / (n−1)!

最后答案为 j=1n1f[i][j]j\sum_j=1^n-1 f[i][j] * j

代码

const double eps = 1e-8;
const int mod = 998244353;
const int N = 5e5+10;
ll a[N],l[N],r[N];
ll fac[N],inv[N],Finv[N];
struct
{
    void init()
    {
        fac[0] = 1ll, Finv[0]=1ll,inv[1]=1ll;
        for(int i=2;i<N;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
        for(int i=1;i<N;i++)
        {
            fac[i]=fac[i-1]*i%mod;
            Finv[i]=Finv[i-1]*inv[i]%mod;
        }
    }
    ll C(ll n,ll m)
    {
        if(n<0||m<0||m>n) return 0;
        if(n == m || m == 0) return 1;
        return fac[n] * Finv[m] %mod * Finv[n-m] %mod;
    }
    ll A(ll n,ll m)
    {
        return fac[n] * Finv[n-m] % mod;
    }
}O_O;
ll dp[55][55],n;
ll calc(ll x,ll y) // 前y个中选x个
{
    if(x > y) return 0;
    return fac[y] * Finv[y - x] % mod * fac[n-1-x] %mod * Finv[n-1] % mod;
}
int main()
{
//    __IN;__OUT;
    O_O.init();
   RLL(n);
    FOR(i,1,n) RLL(a[i]);
    FOR(i,1,n)
    {
        _FOR(j,i-1,1) if( a[j] > a[i] ) { l[i] = j;break;}
        FOR(j,i+1,n) if( a[j] > a[i] ) { r[i] = j;break;}
    }
    FOR(i,1,n)
    {
        FOR(j, 1, n - 1) {
            ll a = 0, b = 0;
            if (l[i])a = calc(i - l[i], j);
            if (r[i])b = calc(r[i] - i, j);
            if (l[i] && r[i]) dp[i][j] = (a + b - calc(r[i] - l[i], j)  % mod + mod )%mod;
            else dp[i][j] = a + b;
        }
    }

    FOR(i,1,n)
    {
        if(!l[i] && !r[i]) PLP(n-1);
        else
        {
            ll now = 0;
            FOR(j, 1, n-1)
            {
                now += (dp[i][j] - dp[i][j - 1]) % mod * (j - 1) % mod;
                now %= mod;
            }
            now += mod;
            now %= mod;
            PLP(now);
        }
    }
    return 0;
}