【题解】loj#6433 [PKUSC2018]最大前缀和

一个长为 $n$ 的序列 $a_n$,求这个序列随机打乱后最大前缀和的期望值。

$n ≤ 20, |a_i | ≤ 10^9$

一道让人更透彻地理解动态规划的好题orz

这是个神仙题…

考虑从这个 $dp$ 的本质入手。以下记 $\{a_m\}$ 表示长度为 $m$ 的序列 $a_1,a_2,\cdots a_m$ 。

首先,对于一个最大前缀和 $(p,\{s_n\})$ 表示的是 $s_1,s_2\cdots s_p$ 构成这个序列的最大前缀和,那么有两个性质:

1、对于 $\{s_n\}$ 的任意 $k>p$ 的 $k\sim n$ 后缀,都有 $sum(k\sim n) \leq 0$ 。

2、对于 $\{s_p\}$ (即 $\{s_n\}$ 的 $1\sim p$ 前缀)的任意 $k>1$ 的 $k\sim p$ 后缀,有 $sum(k\sim p)\geq 0$ 。

那么考虑枚举集合 $t$,表示这个集合的全部元素都用来贡献最大前缀和,记 $f_t$ 为满足条件2的排列方案数,$g_t$ 为满足条件1的方案数,那么考虑如何按秩转移。对于已经有的一个排列,考虑在序列最前端加一个数or在序列最后端加一个数,这样我们保证了按秩的同时,可以比较方便地讨论:

1、如果 $sum_t<0$ ,那么就可以向 $\forall \{k\}\operatorname{and} t=\empty,k$ 的 $g_{t\cup\{k\}}$ 贡献 $g_t$ 的方案数,也就是向序列后方添一个数。

2、如果 $sum_t\geq 0$ ,那么就可以向 $\forall \{k\}\operatorname{and} t=\empty,k$ 的 $f_{t\cup\{k\}}$ 贡献 $f_{t}$ 的方案数,也就是向序列前端添一个数。

但是这个地方有个问题,就是如果最大的前缀和为负,他依然有贡献,但是没有统计。考虑一个贪心的性质如果最大前缀和为负,那么肯定最大前缀和只有第一个元素。所以一开始把所有只有一个元素的 $f$ 都置为 $1$ 即可。

这个地方有个很需要学习的地方,就是 刷表法在此处由于和dp的推法一致,也就是在模拟加入一个数的过程,所以刷表会比较自然,而朴素地填表就会出错

嗯,拿小本本记下来了/kel

于是最后答案就是:

以下是向srz学习的dp方式,本质上也是在枚举 $>0$ 后缀:

考虑另一种推 $f$ 的方式,考虑本质上 $f_t$ 计算的是有多少种方案使得 $sum_t$ 成为最大前缀和,那么就可以这么转移:

也就是枚举有多少种不合法的方案,通过子集转移。裸的转移是 $3^n$ 的,但观察到本质上是在做一个集合的对称差,于是可以用 $\rm FWT$ 优化到 $2^nn^2$ 。

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std ;

#define low(x) (x & (-x))

typedef long long LL ;

const int N = 22 ;
const int M = 2000010 ;
const int P = 998244353 ;

int n ;
int m ;
LL ans ;
LL f[M] ;
LL g[M] ;
LL sum[M] ;
int base[N] ;

LL expow(LL a, int b){
LL res = 1 ;
while (b){
if (b & 1)
(res *= a) %= P ;
(a *= a) %= P ; b >>= 1 ;
}
return res ;
}
int main(){
cin >> n ;
m = (1 << n) - 1 ; g[0] = 1ll ;
for (int i = 0 ; i < n ; ++ i) f[1 << i] = 1 ;
for (int i = 1 ; i <= n ; ++ i)
cin >> base[i], sum[1 << (i - 1)] = base[i] ;
for (int i = 1 ; i <= m ; ++ i)
sum[i] = (sum[low(i)] + sum[i ^ low(i)]) % P ;
for (int i = 1 ; i <= m ; ++ i)
if (sum[i] >= 0){
for (int j = 0 ; j < n ; ++ j)
if (!((1 << j) & i)) (f[i | (1 << j)] += f[i]) %= P ;
}
else{
for (int j = 0 ; j < n ; ++ j)
if ((1 << j) & i) (g[i] += g[(1 << j) ^ i]) %= P ;
}
for (int i = 1 ; i <= m ; ++ i)
(ans += sum[i] * f[i] % P * g[m ^ i] % P) %= P ;
cout << (((ans % P) + P) % P) << endl ; return 0 ;
}