bzoj 5369: [Pkusc2018]最大前綴和

Description

小C是一個算法競賽愛好者，有一天小C遇到了一個非常難的問題：求一個序列的最大子段和。
但是小C并不會做這個題，于是小C決定把序列隨機打亂，然后取序列的最大前綴和作為答案。
小C是一個非常有自知之明的人，他知道自己的算法完全不對，所以并不關心正確率，他只關心求出的解的期望值，
現在請你幫他解決這個問題，由于答案可能非常復雜，所以你只需要輸出答案乘上n!后對998244353取模的值，顯然這是個整數。
注：最大前綴和的定義：i∈[1,n],Sigma(aj)的最大值,其中1<=j<=i

Solution

注意到前綴和的取值只有 \(2^n\) 種.
然后可以枚舉每一個集合的元素當最大前綴和 , 那么這個集合的元素排列之后每一個后綴都必須大于 \(0\) , 且這個集合的補集排列之后必須保證每一個前綴和都小于 \(0\).
那么狀壓 \(DP\) 就行了 , 設 \(f[i]\) 表示集合 \(i\) 作為最大前綴和且排列之后每個后綴都大于 \(0\) 的方案數 , \(g[i]\) 表示集合 \(i\) 中元素排列之后每個前綴都小于 \(0\) 的方案數.
強制 \(f,g\) 必須在合法的時候才能轉移就行了.

#include<bits/stdc++.h>
using namespace std;
const int N=25,mod=998244353;
int f[1<<20],n,a[N],m,g[1<<20],sum[1<<20];
int main(){freopen("pp.in","r",stdin);freopen("pp.out","w",stdout);cin>>n,m=(1<<n)-1;for(int i=0;i<n;i++)cin>>a[i];for(int i=0;i<n;i++)for(int j=0;j<=m;j++)if(j>>i&1)sum[j]+=a[i];for(int i=0;i<n;i++)f[1<<i]=1,g[1<<i]=1;for(int i=0;i<=m;i++){if(sum[i]>0){for(int j=0;j<n;j++)if(~i>>j&1)f[i^(1<<j)]=(f[i^(1<<j)]+f[i])%mod;}else{for(int j=0;j<n;j++)if(~i>>j&1)g[i^(1<<j)]=(g[i^(1<<j)]+g[i])%mod;}}g[0]=1;int ans=0;for(int i=0;i<=m;i++)if(sum[m^i]<=0)ans=(ans+1ll*f[i]*sum[i]%mod*g[m^i])%mod;cout<<(ans+mod)%mod;return 0;
}