洛谷P6046 纯粹容器题解

题意：

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

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

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

两个容器 $i$ 和 $j$ 位置相邻当且仅当不存在 $k$ 满足 $i<k<j$ 且 $k$ 号容器未被击倒。

输入格式：

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1, a_2,\cdots,a_n$，意义见题目描述。

输出格式：

一行 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个容器的存活轮数的期望。为了避免浮点误差，保证答案可以表示为最简分数 $\frac{p}{q}$，你只需要输出一个 $x (0 \leq x < 998244353)$ 使得 $qx \equiv p \pmod {998244353}$。

数据范围：

对于所有测试点，保证 $1 \leq n \leq 50$，$1 \leq a_i \leq n$，$a_i$ 两两不同。

本题之所以评级为提高+/省选− ，是因为 $n$ 出太小了。实际上本题可以线性做。

记一个点至多存活的轮数 $t_i$ 的期望为 $\mathrm{E}(t_i)$ ，则根据期望的定义

$\mathrm{E}(t_i) = \sum_{x \ge 1} \mathrm{Pr}(t_i = x)\cdot 1$

设操作 $x$ 轮，则总方案数为 $\mathrm{A}_{n-1}^x=x!\binom{n-1}{x}$ ，就是在 $n-1$ 个空里找 $x$ 个合并，顺序无要求。

显然一个数什么时候被打死，取决于它左右最近的比它大的数，这个可以用单调栈预处理出。

不妨设左侧的那个与 $i$ 的距离为 $a$ ，右侧的那个与 $i$ 的距离为 $b$ ，则合法的方案数为

$x! \sum_{i + j + k = x\,\land\,i \ne a\,\land\,j\ne b} \binom{a}{i}\binom{b}{j}\binom{n-1-a-b}{k}$

这个式子的意思就是，在左侧选 $i$ 个合并，右侧 $j$ 个，然后其他的随便什么合并 $k$ 次，顺序无要求。

直接做应该也能过，不过就没什么意思了。考虑优化。

可以发现后面的一堆组合数可以写成生成函数的形式，如下

$x!\left[t^x\right]\left((1+t)^a-t^a\right)\left((1+t)^b-t^b\right)(1+t)^{n-1-a-b}$

把它展开以后，用下二项式定理就可以得到

$x!\left(\binom{n-1}{x}-\binom{n-1-a}{x-a}-\binom{n-1-b}{x-b}+\binom{n-1-a-b}{x-a-b}\right)$

代回去就是

$\mathrm{Pr}(t_i = x) = \frac{x!\left(\binom{n-1}{x}-\binom{n-1-a}{x-a}-\binom{n-1-b}{x-b}+\binom{n-1-a-b}{x-a-b}\right)}{x!\binom{n-1}{x}}$

直接做应该是 $\mathcal{O}(n^2)$ 的，~~不过都到想这了~~，继续考虑优化。

代回去求和

$\mathrm{E}(t_i) = \sum_{x\ge 1}\frac{x!\left(\binom{n-1}{x}-\binom{n-1-a}{x-a}-\binom{n-1-b}{x-b}+\binom{n-1-a-b}{x-a-b}\right)}{x!\binom{n-1}{x}}$

可以发现，如果我们能预处理出下面这坨，就可以 $\mathcal{O}(1)$ 算出答案了

$\sum_{x=1}^{n-1} \frac{\binom{n-1-i}{x-i}}{\binom{n-1}{x}} \quad (i \ne 0)$

考虑暴力拆开

$\begin{aligned} & =\sum_{x=1}^{n-1} \frac{x!(n-1-i)!}{(x-i)!(n-1)!} \\ & =\frac{1}{(n-1)^{\underline{i}}} \sum_{x=1}^{n-1} x^{\underline{i}} \\ & =\frac{1}{(n-1)^{\underline{i}}} \frac{n^{\underline{i + 1}}}{i+1} \\ & =\frac{n}{i+1} \\ & \end{aligned}$

这里 $n^{\underline{i}}$ 表示下降阶乘幂 (Falling factorial power)，详见《具体数学》 2.6 有限微积分和无限微积分

那么这道题就做完了，时间复杂度 $\mathcal{O}(n)$ ，注意特判 $a,b$ 不存在的情况。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 998244353;
typedef pair<int,int> pii;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(55))
#define Fi first
#define Se second

stack<pii> stk1, stk2;
int a[N], inv[N], ans[N], nxt[N], pre[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n; inv[1] = 1;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 2; i <= n; i++) inv[i] = inv[mod % i] * (mod - mod / i) % mod;
    for(int i = 0; i < n; i++) ans[i] = n * inv[i + 1] % mod;
    for(int i = 1; i <= n; i++) { nxt[i] = n + 1, pre[i] = 0; }
    for(int i = 1; i <= n; i++)
    {
        while(!stk1.empty() && stk1.top().Fi < a[i]) {
            nxt[stk1.top().Se] = i; stk1.pop();
        }
        stk1.push({a[i], i});
    }
    for(int i = n; i >= 1; i--)
    {
        while(!stk2.empty() && stk2.top().Fi < a[i]) {
            pre[stk2.top().Se] = i; stk2.pop();
        }
        stk2.push({a[i], i});
    }
    for(int i = 1; i <= n; i++)
    {
        vector<int> dis;
        if(pre[i] != 0) dis.push_back(i - pre[i]);
        if(nxt[i] != n + 1) dis.push_back(nxt[i] - i);
        if(dis.empty()) cout << n - 1 << ' ';
        else if(dis.size() == 1) {
            int x = dis[0], w = (n - 1 - ans[x] + mod) % mod;
            cout << w << ' ';
        }else {
            int x = dis[0], y = dis[1];
            int w = (n - 1 + mod - ans[x] + mod - ans[y] + ans[x + y]) % mod;
            cout << w << ' ';
        }
    }
    return 0;
}