状压

· · 题解

火箭连接大脑，暴力代替思考！

题目问的是一个序列的所有 n! 种排列的最大非空前坠和之和，看到题解区 n\le20 我们可以想到状压。

后面这一段和其他题解相同。

定义 sum_S=\sum_{i\in S}a_i，f_S 为 [a_{i\in S}] 的 |S|! 种排列中满足任意后缀和 \ge0 的排列方案数，g_S 为 [a_{i\in S}] 的 |S|! 种排列中满足任意前缀和 <0 的排列方案数。

可以得出转移方程

f_S=[sum_S\ge0]\times\sum_{i\in S}f_{\complement_Si} g_S=[sum_S<0]\times\sum_{i\in S}g_{\complement_Si}

其中初始化为 f_0=g_0=1。

随后我们假设一个序列的贡献只产生再最长的最大前缀上。

我们的答案就是 \sum_{S\subseteq\{1\dots n\}}sum_S\times f_S\times g_{\complement_{\{1\dots n\}}S}，这个是好理解的。

我们开心的码完代码发现只有 55 分，为什么，重新观察刚才的思考过程，我们发现我们会将『所有非空前缀和都小于 0』的排列的答案以 0 计入，但是这是错误的。

为了处理这个，其他题解开始各显神通，但是其中一种神通似乎都没有说，这里我要说一下这种方法（这也是我写这篇题解的目的）。

题目要求找『最大非空前缀和之和』而我们求的是『最大前缀和之和』，我们简单思考就可以发现『最大非空前缀和之和』可以转化为『第一个元素加后面长为 n-1 的序列的最大前缀和之和』，我们就显然可以枚举第一个元素是什么，然后做上面的 dp 就好了。

时间复杂度是抽象的 O(n^22^n)。

#include <bits/stdc++.h>
#define int long long
#define MAXN 1200005
#define mod 998244353
using namespace std;
int n, A[MAXN], sum[MAXN], ans, f[MAXN], g[MAXN], cur_fir, a[1005][1005];
void solve(int *a) { // 直接调用获得 55pts 高分
    memset(sum, 0, sizeof(sum));
    memset(f, 0, sizeof(f));
    memset(g, 0, sizeof(g));
    for (int i = 1; i <= n; i++) { // 枚举，算出 sum
        for (int j = 0; j < (1 << n); j++) {
            if (j & (1 << i - 1)) {
                sum[j] += a[i];
            }
        }
    }
    f[0] = g[0] = 1;
    for (int i = 1; i < (1 << n); i++) { // 按照上面的递推公式算出 f 和 g
        for (int j = 1; j <= n; j++) {
            if (i & (1 << j - 1)) {
                if (sum[i] >= 0) {
                    f[i] += f[i ^ (1 << j - 1)];
                    f[i] %= mod;
                }
                if (sum[i] < 0) {
                    g[i] += g[i ^ (1 << j - 1)];
                    g[i] %= mod;
                }
            }
        }
    }
    for (int i = 0; i < (1 << n); i++) { // 按照上面的计算答案公式算出答案，记得 sum 要加一个当前的第一个元素
        ans += (sum[i] + cur_fir) % mod * f[i] % mod * g[(1 << n) - 1 ^ i] % mod;
        ans %= mod;
    }
}
signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> A[i]; // 这个是原始的序列
    }
    n--; // 方便操作
    for (int i = 1; i <= n + 1; i++) {
        cur_fir = A[i];
        int *b = a[i]; // 拷贝一下原始序列，A 删掉 A[i] 然后存进 b
        for (int j = 1; j < i; j++) {
            b[j] = A[j];
        }
        for (int j = i + 1; j <= n + 1; j++) {
            b[j - 1] = A[j];
        }
        solve(b);
    }
    cout << (ans % mod + mod) % mod;
    return 0;
}