原题链接：https://www.luogu.com.cn/problem/P5369
题意解读：求n个数所有排列的最大前缀和之和，求期望要除以n！，此题简化后不需要除以n！。
解题思路：
1、暴力思路
枚举n个数的全排列，针对每个排列求一遍前缀和，取最大值，加总，复杂度n*n!，n最大20，爆了。
2、状压DP
直接考虑最大前缀和的取值，可能性就是在n个数中任选0~n个数之和，一共2^n种可能；
然后，针对每一种最大前缀和，求出一共有多少个排列符合要求。
对于一个排列1~n，如果1~i是最大前缀和，那么这个排列有如下两个性质：
性质一：1~i的数的任何排列，都符合后缀和>=0，这样才能保证最大前缀和取到i；
性质二：i+1~n的数的任何排列，都符合前缀和<0，这样才能保证最大前缀和不取i之后的数。
基于以上性质，设状态s，其中位置是1表示选了的数，sum[s]表示s中所选数之和，
设f[s]表示s中所有数组成的排列中，最大前缀和是sum[s]的方案数；
设g[s]表示s中所有数组成的排列中，最大前缀和<0的方案数；
这样，一个排列可以拆分成s和((1 << n) - 1) ^ s两部分来考虑，两部分的数量就是f、g的含义，乘法原理乘起来就是总的数量，
那么，答案显然是：∑ sum[s] * f[s] * g[((1 << n) - 1) ^ s]
如何计算f？
基于性质一，如果n个数的排列中，最大前缀和为sum[s]，如果sum[s]>=0，那么在s中所有数排列前面增加任意一个数，得到新的状态t，这时最大前缀和则是sum[t]，说明f[s]对f[t]产生贡献。
因此有：f[t] += f[s]，（t = s | (1 << i)，(s >> i & 1) == 0）
如何计算g?
基于性质二，如果s中所有数的最大前缀和sum[s]<0，那么可以枚举排在最后一个的数，如果除去排在最后一个的数，其余的数最大前缀和依然<0，设其余数的状态为t，说明g[t]对g[s]产生贡献。
因此有：g[s] = ∑ g[t]，（t = s - (1 << i), (s >> i & 1) != 0）
编程时注意取模。
100分代码：
#include <bits/stdc++.h>
using namespace std;const int N = 20, MOD = 998244353;
int f[1 << N], g[1 << N];
int sum[1 << N];
int a[N];
int n, ans;int main()
{cin >> n;for(int i = 0; i < n; i++) cin >> a[i];//预处理sumfor(int i = 0; i < 1 << n; i++)for(int j = 0; j < n; j++)if(i >> j & 1) sum[i] += a[j];//计算ffor(int i = 0; i < n; i++) f[1 << i] = 1; //集合只有一个数的方案数是1for(int s = 0; s < 1 << n; s++){if(sum[s] >= 0)for(int i = 0; i < n; i++)if(!(s >> i & 1))f[s | (1 << i)] = (f[s | (1 << i)] + f[s]) % MOD;}//计算gg[0] = 1; //初始化for(int s = 1; s < 1 << n; s++)if(sum[s] < 0)for(int i = 0; i < n; i++)if(s >> i & 1)g[s] = (g[s] + g[s - (1 << i)]) % MOD;for(int s = 0; s < 1 << n; s++)ans = (ans + 1ll * sum[s] * f[s] % MOD * g[((1 << n) - 1) ^ s] % MOD) % MOD;cout << (ans + MOD) % MOD; //避免负数return 0;
}