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\) 。

注意

時刻取模。