[PKUSC2018] 最大前缀和

Luogu P5369

题目描述

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

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

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

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

Solution

考虑一个位置上的值想要成为最大前缀和需要满足什么条件。不难发现这个位置开始之后所有位置的前缀和都应该为非正数，且这个位置开始之前的所有位置的前缀和都应该为非负数。那么只要想办法 DP 出来前半段的方案数 \(f\) 和后半段的方案数 \(g\) 然后相乘即可。

这个 DP 方法类似 CF327E。设 \(f(S)\) 表示当前选定数的集合为 \(S\) 的所有前缀和都非正的方案数。那么转移的时候只需要判断 \(x+\displaystyle\sum\limits_{v\in S} v\) 是否非正即可。\(g\) 的转移同理。

最后枚举在前半段的集合 \(t\)，设全集为 \(U\)，那么答案即为 \(\displaystyle\sum\limits_{t\subseteq U}g(t)\times f(\complement_Ut)\)。

时间复杂度 \(\mathcal O(n2^n)\)。

int N, A[_N];
int val[_M];
mint f[_M], g[_M];
signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> N;
    For(i, 1, N) cin >> A[i];
    int lim = 1 << N;
    For(S, 0, lim - 1) {
        For(i, 1, N) if (S >> (i - 1) & 1)
            val[S] += A[i];
    }
    f[0] = g[0] = 1;
    For(S, 0, lim - 1) {
        For(i, 1, N) if (!(S >> (i - 1) & 1)) {
            if (val[S] >= 0 || S == 0) f[S|(1<<(i-1))] += f[S];
            if (A[i] + val[S] < 0) g[S|(1<<(i-1))] += g[S];
        }
    }
    mint ans = 0;
    For(S, 1, lim - 1) {
        mint tmp = (val[S] % mod + mod) % mod;
        ans += tmp * f[S] * g[(lim-1)^S];
    }
    cout << ans << '\n';
}