A5991. 「PKUSC2018」最大前缀和
编程题
省选/NOI-
知识点
题目描述
小 C 是一个算法竞赛爱好者，有一天小 C 遇到了一个非常难的问题：求一个序列的最大子段和。
但是小 C 并不会做这个题，于是小 C 决定把序列随机打乱，然后取序列的最大前缀和作为答案。
小 C 是一个非常有自知之明的人，他知道自己的算法完全不对，所以并不关心正确率，他只关心求出的解的期望值，现在请你帮他解决这个问题，由于答案可能非常复杂，所以你只需要输出答案乘上 $n!$ 后对 $998244353$ 取模的值，显然这是个整数。
注：最大前缀和的定义：$\forall i \in [1,n]$，$\sum_{j=1}^{i}a_j$的最大值。
但是小 C 并不会做这个题，于是小 C 决定把序列随机打乱，然后取序列的最大前缀和作为答案。
小 C 是一个非常有自知之明的人，他知道自己的算法完全不对，所以并不关心正确率，他只关心求出的解的期望值，现在请你帮他解决这个问题，由于答案可能非常复杂，所以你只需要输出答案乘上 $n!$ 后对 $998244353$ 取模的值，显然这是个整数。
注：最大前缀和的定义：$\forall i \in [1,n]$，$\sum_{j=1}^{i}a_j$的最大值。
输入格式
第一行一个正整数 $n$，表示序列长度。
第二行 $n$ 个数，表示原序列 $a[1..n]$，第 $i$ 个数表示 $a[i]$ 。
第二行 $n$ 个数，表示原序列 $a[1..n]$，第 $i$ 个数表示 $a[i]$ 。
输出格式
输出一个**非负整数**，表示答案。
输入输出样例
输入 #1
2 -1 2
输出 #1
3
说明/提示
## 数据范围
对于$10\%$的数据，有$1\leq n\leq 9$。
对于$40\%$的数据，有$1\leq n\leq 15$。
另有$10\%$的数据，满足$a$中最多只有一个负数。
另有$10\%$的数据，满足$|a[i]|\leq 2$。
对于$100\%$的数据，满足$1\leq n\leq 20$，$\sum_{i=1}^{n}|a[i]|\leq 10^9$。
对于$10\%$的数据，有$1\leq n\leq 9$。
对于$40\%$的数据，有$1\leq n\leq 15$。
另有$10\%$的数据，满足$a$中最多只有一个负数。
另有$10\%$的数据，满足$|a[i]|\leq 2$。
对于$100\%$的数据，满足$1\leq n\leq 20$，$\sum_{i=1}^{n}|a[i]|\leq 10^9$。