← 返回题单
题单练习 概率与期望DP
← 上一题 下一题 →

A7133 | 纯粹容器

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

题目背景



白王正在挑选容器。

题目描述



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

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

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

两个容器 $i$ 和 $j$ 位置相邻当且仅当不存在 $k$ 满足 $ikj$ 且 $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
3
3 1 2
输出 #1
2 0 1
输入 #2
3
1 2 3
输出 #2
499122177 499122177 2
输入 #3
5
1 4 2 3 5
输出 #3
499122178 249561091 665496236 582309207 4
C++ 编辑器
输入
输出