P5369 最大前缀和
题目
题目描述
小 C 是一个算法竞赛爱好者，有一天小 C 遇到了一个非常难的问题：求一个序列的最大子段和。
但是小 C 并不会做这个题，于是小 C 决定把序列随机打乱，然后取序列的最大前缀和作为答案。
小 C 是一个非常有自知之明的人，他知道自己的算法完全不对，所以并不关心正确率，他只关心求出的解的期望值，现在请你帮他解决这个问题，由于答案可能非常复杂，所以你只需要输出答案乘上 \(n!\) 后对 \(998244353\) 取模的值，显然这是个整数。
注：最大前缀和的定义：\(\forall i \in [1,n]\)，\(\sum_{j=1}^{i}a_j\)的最大值。
对于\(100\%\)的数据，满足\(1\leq n\leq 20\)，\(\sum_{i=1}^{n}|a[i]|\leq 10^9\)。
思路
看到 \(n\le 20\) 想到状压dp。
考虑集合 \(S\) 的元素作为前缀和的方案数，设 \(f_S\) 表示 \(S\) 的元素作为前缀的方案数， \(g_S\) 表示 \(S\) 中的元素作为后缀不改变最大前缀，即 \(S\) 中的元素的最大前缀和小于 \(0\) 的方案数，\(sum_S\) 表示 \(S\) 中的元素的和。则有：
\(sum\) 可以直接求， \(g\) 容易求，有 \(g_S=\sum g_T [T=S-(w)\and sum_S>=0]\) 。
若按照从前往后的顺序求 \(f\) ，需要枚举最大前缀和的位置，难以转移。
考虑正难则反。向后插入点难以处理，则在前面插入点。
若当前排列 \(a_1,a_2,a_k\) 为最大前缀和，则 \(a_2,a_k\) 也为最大前缀和。
因此有 \(f_S\) 转移到 \(f_{T=S\or w}\) 的条件为 \(sum_T>a_w\) 。
注意
时刻取模。