#P9582. DDL

    ID: 6198 传统题 2000ms 512MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2500省选/NOI-排序贪心势能分析贡献法交换求和顺序懒标记线段树模逆元

DDL

题目描述

菜菜的 Jayce 认为自己很水,事实上确实是这样的。

有 nn 位神仙,第 ii 位的神仙度为 aia_i。Jayce 打算选择一个区间 [l,r](1≤l≤r≤n)[l, r](1 \le l \le r \le n),并吸收这段区间大佬的神仙度。

具体的,神仙度会从高浓度扩散到低浓度。Jayce 一开始的神仙度是 s=0s = 0,每次 Jayce 可以选择一个区间中的神仙 i∈[l,r]i \in [l, r],并疯狂膜拜该神仙,令 ss 和 aia_i 都变为原先两者的平均值,即 s+ai2\frac {s+a_i} 2。Jayce 可以进行至多 LIM=1145141919810LIM=114514^{1919810} 次膜拜操作,定义区间 [l,r][l, r] 的神仙度是:Jayce 通过至多 LIMLIM 次膜拜操作能得到的最大 ss(初始 s=0s = 0)。

Jayce 想知道所有 n(n+1)2\frac {n(n+1)}{2} 个区间的神仙度之和对 998244353998244353 取模后的值。

输入格式

第一行一个正整数 nn,表示神仙的数量。

第二行 nn 个正整数 aia_i,表示每个神仙的神仙度。

输出格式

输出一个数表示答案。

样例

样例 1

3
1 2 3
623902729

取模前答案为 678\frac {67} 8。

样例 2

6
1 1 4 5 1 4
889061433

样例 3

18
9 9 8 2 4 4 3 5 3 9 9 3 2 4 4 8 5 3
681808275

子任务

对于 100%100\% 的数据,满足 1≤n≤5×1051\le n\le 5\times 10^5,1≤ai≤1091\le a_i\le 10^9。

  • 子任务 11(1010 分):n≤10n\le 10。
  • 子任务 22(2020 分):n≤100n\le 100,依赖子任务 11。
  • 子任务 33(2020 分):n≤5×103n\le 5\times 10^3,依赖子任务 1,21,2。
  • 子任务 44(2020 分):n≤105n\le 10^5,依赖子任务 1,2,31,2,3。
  • 子任务 55(2020 分):ai≤100a_i\le 100。
  • 子任务 66(1010 分):无特殊限制,依赖子任务 1,2,3,4,51,2,3,4,5。