[PKUSC2018]最大前缀和LuoguP5369题目描述小C是一个算法竞赛爱好者，有一天小C遇到了一个非常难的问题：求一个序列的最大子段和。但是小C并不会做这个题，于是小C决定把序列随机打乱，然后取序列的最大前缀和作为答案。小C是一个非常有自知之明的人，他知道自己的算法完全

传送门题目大意给定一个序列，求任意重排\(n!\)中情况所以的最大非空前缀和的和。模\(998244353\)。\(n\e20\)，\(\sum|a_i|\le10^9\)题目解析考虑最大前缀和的性质，有：对于最大前缀和部分，所有的真后缀大于等于零。（最大前缀和可能小于零）对于不在最大前缀和的后半部分，所

P5369[PKUSC2018]最大前缀和题目要我们求每一种排列的最大前缀和，不妨考虑先确定最大前缀和，再计算它的方案数，设\(U\)为全集，那么答案就为\(\sum_{S\subseteqU}sum[S]*f

题意给定一个序列\(a\)，求\(a\)的所有排列的最大前缀和的和。\(1\len\le20\)。Solution考虑到\(n\)很小的性质，想到状压。先考虑一手，最大前缀和应该满足什么条件

先规定一些东西：若存在多个\(p\)使得\(\sum_{i=1}^{p}{a_i}\)最大，默认最大（即最靠右）的一个\(p\)是它的最大前缀和的位置。\(U\)表示全集。假设\(p\)是最大前缀