LibreOJ 6433.「PKUSC2018」最大前缀和

期望还乘 n!n!……极其迷惑……
所以实际上就是统计所有排列的最大前缀和之和。

考虑把得到的排列的前缀和以最大的那一项分割为两个排列,那么如果单取后一半的话,每一项的前缀和一定都 0\le 0(否则拼起来就会出现更大的前缀和)。
于是考虑设两个状态 fS,gSf_S,g_S,分别表示在集合 SS 中的数的排列的最大前缀和为 sumSsum_S 的方案数和在集合 SS 中的排列的前缀和都 0\le 0 的方案数。
其中 sumS=iSaisum_S = \sum\limits_{i \in S} a_i

显然 gg 更容易转移。

然后考虑 ff,可以通过在排列前面加数的方式转移。

如果 sumS0sum_S \le 0,那么就会出现更大的前缀和(即新加的 kk)。

然后随手统计答案就完事了。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <cstdio>
#define lowbit(x) ((x) & -(x))
using namespace std;
const int N = 20;
const int mod = 998244353;
int n,a[N + 5],full;
int lg[(1 << N) + 5];
long long sum[(1 << N) + 5];
int f[(1 << N) + 5],g[(1 << N) + 5],ans;
int main()
{
scanf("%d",&n),full = (1 << n) - 1;
for(register int i = 2;i <= full;++i)
lg[i] = lg[i >> 1] + 1;
for(register int i = 1;i <= n;++i)
scanf("%d",a + i);
for(register int i = 1;i <= full;++i)
sum[i] = sum[i ^ lowbit(i)] + a[lg[lowbit(i)] + 1];
for(register int i = 1;i <= n;++i)
f[1 << i - 1] = 1;
g[0] = 1;
for(register int i = 0;i <= full;++i)
if(sum[i] > 0)
for(register int j = 1;j <= n;++j)
if(!((1 << j - 1) & i))
f[i | (1 << j - 1)] = (f[i | (1 << j - 1)] + f[i]) % mod;
for(register int i = 0;i <= full;++i)
for(register int j = 1;j <= n;++j)
if(!((1 << j - 1) & i) && sum[i | (1 << j - 1)] <= 0)
g[i | (1 << j - 1)] = (g[i | (1 << j - 1)] + g[i]) % mod;
for(register int i = 0;i <= full;++i)
ans = (ans + (long long)f[i] * g[full ^ i] % mod * (sum[i] + mod) % mod) % mod;
printf("%d\n",ans);
}

arknights