洛谷P5369 [PKUSC2018]最大前缀和题解

题目链接：P5369 [PKUSC2018]最大前缀和

题意：

cxy 是一个算法竞赛爱好者，有一天 cxy 遇到了一个非常难的问题：求一个序列的最大子段和。

但是 cxy 并不会做这个题，于是 cxy 决定把序列随机打乱，然后取序列的最大前缀和作为答案。

cxy 是一个非常有自知之明的人，她知道自己的算法完全不对，所以并不关心正确率，她只关心求出的解的期望值，现在请你帮她解决这个问题，由于答案可能非常复杂，所以你只需要输出答案乘上 \(n!\) 后对 \(998244353\) 取模的值，显然这是个整数。

注：最大前缀和的定义：\(\forall i \in [1,n],~\sum_{j=1}^{i}a_j\)的最大值。

输入格式：

第一行一个正整数 \(n\)，表示序列长度。

第二行 \(n\) 个数，表示原序列 \(a\)，第 \(i\) 个数表示 \(a_i\) 。

输出格式：

输出一个非负整数，表示答案。

数据范围：

满足\(1\leq n\leq 20,~\sum_{i=1}^{n}|a_i|\leq 10^9\)。

期望+状压dp好题。

记 \(S_A\) 为集合 \(A\) 内所有元素的和，即 \(\sum a_i~(a_i \in A)\) 。

注意到一个 \(p\) 使得 \(S_p\) 作为最大前缀和时一定有 \[ \max_{1\le l < p}\left\{\sum_{1\le i \le l}a_i\right\}\le S_p \quad\bigwedge\quad \max_{p < r \le n}\left\{\sum_{p+1\le i \le r}a_i\right\} < 0 \] 即 \[ \max_{1\le l < p}\left\{S_l\right\}\le S_p \,\wedge\, \max_{p < r \le n}\left\{S_r - S_p\right\} < 0 \] 设 \(f_A\) 表示集合 \(A\) 中的所有元素组成的排列，且最大前缀和等于 \(S_i\) 的方案数。

设 \(g_A\) 表示集合 \(A\) 中的所有元素组成的排列，且最大前缀和小于 \(0\) 的方案数。

则最终答案为（记 \(U\) 为全集） \[ \sum_{A\subseteq U} S_A\times f_A\times g_{U\setminus A} \] 解释一下这里的意义，我们枚举最大前缀和的集合 \(A\) 作为前半部分

后半部分根据刚刚提到的性质可知，最大前缀和小于 \(0\) ，而 \(S_A\) 是贡献。

考虑 \(f_A\) 的转移。这个适用刷表法转移

考虑在集合 \(A\) 的排列的最前面加入一个数 \(k\notin A\) ，则（这里用 \(a\uparrow b\) 表示 a += b ） \[ f_{A \cup k} \uparrow [S_A \ge 0] \times f_A \] 注意这里要 \(S_A \ge 0\) 才能产生贡献，原因还是一开始讲的性质。

考虑 \(g_A\) 的转移，这个适用填表法转移，则 \[ g_A = \left[S_A < 0\right]\times \sum_{k \in A} g_{A\setminus\{k\}} \] 时间复杂度 \(\mathcal{O}(n2^n)\)

代码：（~~一不小心写了个取模全家桶~~）

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 998244353;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
void add(int &x,int y) { (x += y) >= mod ? x -= mod : 0; }
int &Mod(int &x) { return (x = (x < 0 ? (x % mod + mod) : (x % mod))); }
#define N ((int)(25))
#define L ((int)((1 << 20) + 15))
#define lowbit(x) ((x)&(-(x)))

int n,mx,sum[L],f[L],g[L];
int mul(int cnt, ...)
{
    va_list ptr; va_start(ptr,cnt); int res = 1;
    for(int i=0; i<cnt; i++) res = res * va_arg(ptr,int) % mod;
    va_end(ptr); return res;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n; mx = (1 << n) - 1;
    for(int i=0; i<n; i++)
        { cin >> sum[1 << i]; f[1 << i] = 1; }
    for(int i=1; i<=mx; i++)
        sum[i] = sum[i ^ lowbit(i)] + sum[lowbit(i)];
    g[0] = 1;
    for(int i=1; i<=mx; i++)
    {
        if(sum[i] >= 0)
        {
            for(int j=0; j<n; j++)
                if(!(i & (1 << j))) add(f[i | (1 << j)], f[i]);
        }else
        {
            for(int j=0; j<n; j++)
                if(i & (1 << j)) add(g[i], g[i ^ (1 << j)]);
        }
    }
    int res = 0;
    for(int i=1; i<=mx; i++)
        add(res, mul(3, sum[i], f[i], g[mx ^ i]));
    cout << Mod(res) << '\n'; // 注意可能为负，要转成正的
    return 0;
}