F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 5369. -- [Pkusc2018]最大前缀和

5369: [Pkusc2018]最大前缀和

Time Limit: 20 Sec  Memory Limit: 512 MB
Submit: 262  Solved: 134
[Submit][Status][Discuss]

Description

小C是一个算法竞赛爱好者,有一天小C遇到了一个非常难的问题:求一个序列的最大子段和。
但是小C并不会做这个题,于是小C决定把序列随机打乱,然后取序列的最大前缀和作为答案。
小C是一个非常有自知之明的人,他知道自己的算法完全不对,所以并不关心正确率,他只关心求出的解的期望值,
现在请你帮他解决这个问题,由于答案可能非常复杂,所以你只需要输出答案乘上n!后对998244353取模的值,显然这是个整数。
注:最大前缀和的定义:i∈[1,n],Sigma(aj)的最大值,其中1<=j<=i

Input

第一行一个正整数nnn,表示序列长度。
第二行n个数,表示原序列a[1..n],第i个数表示a[i]。
1≤n≤20,Sigma(|Ai|)<=10^9,其中1<=i<=N

Output

输出一个非负整数,表示答案。

Sample Input

2
-1 2

Sample Output

3

HINT

Source

[Submit][Status][Discuss]

HOME Back