解题思路

设样本读数序列为 $a_1,\dots,a_n$ 。对每个 $k$ （ $1\le k\le n$ ），求所有长度为 $k$ 的子序列 $b$ 的峰值 $f(b)=\max(b)$ 之和，答案对 $998244353$ 取模。

将读数按非降序排序，记为 $A_1\le A_2\le \cdots\le A_n$ 。把每个长度为 $k$ 的子序列唯一地归属给其最大值在排序后的最右位置 $i$ 。当峰值归属在位置 $i$ 时，其余 $k-1$ 个元素只能从 $[1,i-1]$ 中任取（都不超过 $A_i$ ），共有

\binom{i-1}{k-1}

题目内容

实验室里有 $n$ 份依次编号的检测样本，第 $i$ 份的读数为 $a_i$ 。从这些样本中删除任意份（可以不删，也可以全删），并保持剩余样本的相对顺序，得到一个子序列。

定义长度为 $m$ 的子序列 $b$ 的峰值为 $f(b)=\max(b_1,b_2,\ldots,b_m)$ 。对于每一个 $k=1,2,\ldots,n$ ，求所有长度为 $k$ 的子序列的峰值之和。答案可能很大，请对 $998244353$ 取模后输出。

约束：样本份数不超过 5000，每份读数为不超过 10^9 的正整数。