洛谷P6046 纯粹容器 题解
题目链接：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;
}参考文献：
