上午的国庆大阅兵有意思 Description https://loj.ac/problem/6433 Solution 看数据范围认解法 首先在每种情况出现概率相同的情况下， \(期望 \times 方案数 = 权值和\) ，即题意就是让你求所有排列
- 上午的国庆大阅兵有意思
Description
https://loj.ac/problem/6433
Solution
看数据范围认解法
首先在每种情况出现概率相同的情况下， \(期望 \times 方案数 = 权值和\)，即题意就是让你求所有排列的最大前缀和的总和……
我们可以枚举哪些数是最大前缀，显然这些数内部任意交换顺序、其它数内部任意交换顺序 都不会改变这个最大前缀。
一些数要排到前面去成为最大前缀，条件是该前缀除整段外的所有后缀和 \(\gt 0\)（因为最大前缀长度不能是 \(0\)），后面的所有前缀和 \(\le 0\)。
（一个 \(\gt 0\)，一个 \(\le 0\) 是因为对于一种排列，若有多个前缀和均为最大，我们只根据最短的前缀统计一次该排序。也可以根据最长的前缀，即一个 \(\ge 0\)，一个 \(\lt 0\)）
设 \(f(i)\) 表示集合 \(i\) 的数有多少种排列满足所有后缀和 \(\gt 0\)，\(g(i)\) 表示集合 \(i\) 的数有多少种排列满足所有前缀和 \(\le 0\)。
\(f\) 的转移是每次往前加一个数，\(g\) 的转移是每次往后加一个数。
最后把 \(f\) 和 \(g\) 卷起来就好了。