首先对于一个序列$[a_1,a_n]$，设最大前缀和的位置为$p$，那么序列$[a_{p+1},a_n]$的任意一个前缀必须都$<=0$。否则的话你用最大前缀和随便加上$[a_{p+1},a_n]$中$>0$的一个前缀就可以得到新的最大前缀和。
预处理：
$sum[S]$表示集合$S$的数字和。
$f[S]$表示钦定集合$S$当最大前缀的合法方案数。
$g[S]$表示集合$S$任意前缀和$<=0$小于$0$的方案数。
那么显然$ans=\sum sum[S]\times f[S]\times g[S‘]$。其中$S‘$是$S$的补集。
$sum$和$g$都是可以直接求的，那么$f$呢？
可以发现，如果$sum[S]>0$，那么把随便一个数放到这个集合$S$的最前面，这个最大前缀和仍然是可以保证合法的。
$ans$最后忘了取模$WA$了好几发……心态崩了
1 #include<iostream> 2 #include<cstdio> 3 #define N (21) 4 #define MOD (998244353) 5 using namespace std; 6 7 int n,m,a[N],sum[1<<N],cnt[1<<N],f[1<<N],g[1<<N]; 8 9 int main() 10 { 11 scanf("%d",&n); m=(1<<n)-1; 12 for (int i=1; i<=n; ++i) scanf("%d",&a[i]); 13 for (int i=1; i<=n; ++i) 14 for (int S=0; S<=m; ++S) 15 if (S&(1<<i-1)) sum[S]+=a[i], cnt[S]++; 16 17 for (int S=1; S<=m; ++S) 18 { 19 if (cnt[S]==1) {f[S]=1; continue;} 20 for (int i=1; i<=n; ++i) 21 if ((S&(1<<i-1)) && sum[S]-a[i]>0) 22 (f[S]+=f[S^(1<<i-1)])%=MOD; 23 } 24 25 g[0]=1; 26 for (int S=1; S<=m; ++S) 27 { 28 if (sum[S]>0) {g[S]=0; continue;} 29 if (cnt[S]==1) {g[S]=1; continue;} 30 for (int i=1; i<=n; ++i) 31 if (S&(1<<i-1)) 32 (g[S]+=g[S^(1<<i-1)])%=MOD; 33 } 34 int ans=0; 35 for (int S=1; S<=m; ++S) 36 (ans+=1ll*sum[S]*f[S]%MOD*g[m^S]%MOD)%=MOD; 37 ans=(ans%MOD+MOD)%MOD; 38 printf("%d\n",ans); 39 }
BZOJ5369:[PKUSC2018]最大前缀和(状压DP)
原文：https://www.cnblogs.com/refun/p/10158730.html