Divide a Sequence

题目描述

给定一个长度为 $N$ 的数列 $A$ 。有 $2^{N-1}$ 种方法可以将 $A$ 划分为若干个非空的连续子序列 $B_1,B_2,\ldots,B_k$ 。对每一种划分，求下面的值，并输出这些值的和对 $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)$ 和 $\min(B_i)$ 定义为 $B_i$ 中元素的最大值和最小值。

输入从标准输入按照如下格式给出： $N$ $A_1$ $A_2$ $\ldots$ $A_N$

打印这些值的和对 $998244353$ 取模的结果。

3
1 2 3

4
1 10 1 10

10
699498050 759726383 769395239 707559733 72435093 537050110 880264078 699299140 418322627 134917794

877646588

$1 \leq N \leq 3 \times 10^5$ $1 \leq A_i \leq 10^9$ 输入中的所有数值均为整数。将 $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$ 应当被输出。
注意要对 $998244353$ 取模后输出。

标签: AtCoder|abc234G

AtCoder|abc234G