AT_abc234_g [ABC234G] Divide a Sequence

题目描述

给定一个长度为 $N$ 的数列 $A$。

将 $A$ 切分为若干个非空、连续的子序列 $B_1,B_2,\ldots,B_k$ 的方法共有 $2^{N-1}$ 种。对于每一种切分方式，计算如下的值，并将所有切分方式下的结果求和后对 $998244353$ 取模输出：

• $\prod_{i=1}^{k}\ (\max(B_i)-\min(B_i))$

这里，对于某个子序列 $B_i=(B_{i,1},B_{i,2},\ldots,B_{i,j})$，$\max(B_i)$ 表示 $B_i$ 中元素的最大值，$\min(B_i)$ 表示 $B_i$ 中元素的最小值。

输入格式

输入以如下格式从标准输入读入：

$N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

输出所求值的总和对 $998244353$ 取模后的结果。

输入输出样例 #1

输入 #1

3
1 2 3

输出 #1

2

输入输出样例 #2

输入 #2

4
1 10 1 10

输出 #2

90

输入输出样例 #3

输入 #3

10
699498050 759726383 769395239 707559733 72435093 537050110 880264078 699299140 418322627 134917794

输出 #3

877646588

说明/提示

数据范围

• $1\leq N\leq 3\times 10^5$
• $1\leq A_i\leq 10^9$
• 输入均为整数

样例解释 1

将 $A=(1,2,3)$ 切分为非空连续子序列的方法共有 $4$ 种：

• $(1)$ 和 $(2)$ 和 $(3)$
• $(1)$ 和 $(2,3)$
• $(1,2)$ 和 $(3)$
• $(1,2,3)$

对于每种切分方式，$\prod_{i=1}^{k}\ (\max(B_i)-\min(B_i))$ 分别为 $0$、$0$、$0$、$2$，因此总和为 $2$，输出 $2$。

样例解释 3

请注意，输出时需要对 $998244353$ 取模。

由 ChatGPT 4.1 翻译