洛谷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;
}