← 返回题目

题库练习纯粹容器

← 上一题下一题 →

A7133 | $纯粹容器$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

## 题目背景 白王正在挑选容器。 ## 题目描述 白王制造了 $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

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++ 编辑器

输入

输出