题目大意: 给你一个 $n(n\leqslant20)$ 项的数列 $A$, 设重排后的数列为 $A'$, 令 $pre_p=\sum\limits_{i=1}^pA'_i$, 求 $max\{pre_i\}$ 的期望, 乘 $n!$
题解: 令 $f_S$ 为选 $S$ 集合的数, 重排后满足 $\max\{pre_i\}=\sum\limits_{i=1}^{|S|}S_i$ 的方案数,$g_S$ 为选 $S$ 集合数, 重排后满足 $\max\{pre_i\}\leqslant0$ 的方案数. 发现若数列 $B$ 满足 $\sum\limits_{i=1}^{|B|}B_i>0$, 那么任意在它前面插入一个数, 都满足 $f$ 的条件. 若数列 $B$ 满足 $\max\{pre_i\}\leqslant0$, 在它后面插入一个数后, 只要 $\sum\limits_{i=1}^{|B|}B_i\leqslant0$, 就行了.
答案是 $\sum\limits_{S}sum_Sf_Sg_{\bar S}$.
卡点: 无
C++ Code:
- #include
- #define maxn 20
- #define N (1 <<maxn)
- const int mod = 998244353;
- inline void reduce(int &x) { x += x>> 31 & mod; }
- int n;
- int s[maxn], f[N], g[N], sum[N];
- int main() {
- scanf("%d", &n);
- for (int i = 0; i <n; ++i) {
- scanf("%d", s + i);
- f[1 <<i] = 1;
- g[1 << i] = s[i] <= 0;
- }
- const int U = 1 << n, I = U - 1;
- for (int i = 1; i < U; ++i) sum[i] = sum[i & i - 1] + s[__builtin_ctz(i)];
- g[0] = 1;
- for (int i = 0; i < U; ++i) if (__builtin_popcount(i)> 1) {
- for (int j = i; j; j &= j - 1) {
- int k = __builtin_ctz(j), l = i ^ 1 <<k;
- if (sum[i] <= 0) reduce(g[i] += g[l] - mod);
- if (sum[l]> 0) reduce(f[i] += f[l] - mod);
- }
- }
- for (int i = 0; i <U; ++i) reduce(sum[i] %= mod);
- int ans = 0;
- for (int i = 1; i <U; ++i) reduce(ans += static_cast<long long> (sum[i]) * f[i] % mod * g[I ^ i] % mod - mod);
- printf("%d\n", ans);
- return 0;
- }
- [LOJ #6433]「PKUSC2018」最大前缀和
来源: http://www.bubuko.com/infodetail-2929260.html