← 返回题目列表

AtCoder · otemae2019_h

H. 糖果很好吃

中文机器翻译题面 查看原题

配点: 100 点

問題

N 糖果,i 糖果的美味是 A_i 。

f(l,r) (1 \leq l \leq r \leq N) , 从第l 起 对于第 r 号糖果,其定义为在以下条件下所吃的糖果的美味度总和的最大值。 不要连续吃

条件:2 块。也就是说, 一切满足l \leq i < r 一切满足的 i 中,i 与第三颗糖果 你不能同时吃掉 i+1 糖果。

当品尝每种糖果的味道时, 所有满足1 \leq l \leq r \leq N 的元组 关于 (l,r) 关于 f(l,r) 的总和 编写一个程序求除以 998\,244\,353 后的余数。

制約

  • 1 \leq N \leq 200\,000.
  • 1 \leq A_i \leq 1\,000\,000\,000 (1 \leq i \leq N).

小課題

  1. (10 点) N \leq 300.
  2. (20 点) A_i \leq 300 (1 \leq i \leq N).
  3. (70 点)没有额外的限制。

入力

输入是按以下格式从标准输入给出的。

N
A_1 \cdots A_N

出力

在标准输出上, 在1 \leq l \leq r \leq N 的元组 关于 (l,r) 关于 f(l,r) 的总和 编写一个程序求除以 998\,244\,353 后的余数 输出为 1 行。 在


入力例 1

3
1 2 3

出力例 1

15

l=2,r=3 的情况下,2 th 和 3 我两个糖果都吃不下去, 由于最好只吃3 糖果, 它变成f(l,r)=3 。 由于吃第 l=1,r=3 的情况下,1 th 和 3 颗糖果是最佳的,f(l,r)=1+3=4 。 由于吃第

要输出的值为 打印除以 f(1,1)+f(1,2)+f(1,3)+f(2,2)+f(2,3)+f(3,3)=1+2+4+2+3+3=15 。 由于吃第


入力例 2

4
1 100 100 1

出力例 2

805

入力例 3

1
1000000000

出力例 3

1755647

998\,244\,353 后的余数。


入力例 4

10
850534838 749655434 745817507 991867417 645519349 373697182 427765279 182404140 260664174 366393413

出力例 4

554337161