题解 P6059 【纯粹容器 senpai】

· · 题解

显然， 我们可以把每个容器的期望转化成下面这个柿子：

E = \sum_{i = 1} ^ {n - 1}P(i \leq x)

其中 P(i \leq x) 表示容器存活轮数大于等于 i 的概率（即第 i 轮后仍存活的概率）

现在考虑如何计算 P(i \leq x)

（如果有的话）记在容器 c 前第一个比 a_c 大的容器为 pre ，在 c 后第一个比 a_c 大的容器为 next

再来看题意，题目中的操作相当于对一条链随机选一条边进行收缩，可以发现 c 是否存活只与 pre \sim c 和 c \sim next 这两段的边是否全部被选中有关，记 P(A) 为 pre \sim c 这一段全部被选的概率， P(B) 表示 c \sim next 这一段全部被选的概率， P(AB) 表示 pre \sim next 这一段全部被选的概率， d_1 = c - pre， d_2 = next - c 于是得到

\begin{aligned} P(i \leq x) &= 1 - P(A) - P(B) + P(AB) \\ &= 1 - \frac{\binom{n - 1 - d_1}{i - d_1}}{\binom{n-1}{i}} - \frac{\binom{n - 1 - d_2}{i - d_2}}{\binom{n-1}{i}} + \frac{\binom{n - 1 - d_1 - d_2}{i - d_1 - d_2}}{\binom{n-1}{i}} \end{aligned}

怎么感觉写得特别啰嗦

复杂度 O(n^2)

代码：

#include<cstdio>
using namespace std;

typedef long long ll;

const ll mod = 998244353;
const int MAXN = 60;
int a[MAXN], ld[MAXN], rd[MAXN];
ll C[MAXN][MAXN];

inline ll fpow(ll a, ll b){

    ll res = 1;
    while (b){

        if (b & 1)
            res = res * a % mod;
        a = a * a % mod, b >>= 1; 
    }
    return res;
}

inline ll inv(ll a){return fpow(a, mod - 2);}

int main(){
    int N;
    scanf("%d", &N);
    for (int i = 1; i <= N; ++i)
        scanf("%d", &a[i]);
    for (int i = 1; i <= N; ++i){
        for (int j = i - 1; j >= 1; --j)
            if (a[j] > a[i]){
                ld[i] = i - j;
                break;

            }
        for (int j = i + 1; j <= N; ++j)
            if (a[j] > a[i]){
                rd[i] = j - i;
                break;
            }
    }
    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]) % mod;
    }
    ll tmp, pa, pb, pab;
    for (int i = 1; i <= N; ++i){
        tmp = 0;
        for (int j = 1; j < N; ++j){
            pa = pb = pab = 0;
            if (ld[i] && j - ld[i] >= 0)
                pa = C[N - 1 - ld[i]][j - ld[i]] * inv(C[N - 1][j]) % mod;
            if (rd[i] && j - rd[i] >= 0)
                pb = C[N - 1 - rd[i]][j - rd[i]] * inv(C[N - 1][j]) % mod;
            if (ld[i] && rd[i] && j - ld[i] - rd[i] >= 0)
                pab = C[N - 1 - ld[i] - rd[i]][j - ld[i] - rd[i]] * inv(C[N - 1][j]) % mod;
            tmp = (tmp + 1 + mod - pa + mod - pb + pab) % mod;
        }
        printf("%lld ", tmp);
    }
    return 0;
}