题意
对于一个序列 \({b_n}\)，规定：
\[f_min(b) = \prod_{i = 1} ^ n (min_{j = 1} ^ i b_j) \]\[f_max(b) = \prod_{i = 1} ^ n (max_{j = 1} ^ i b_j) \]给定一个序列 \(a\)，求 \(a\) 所有的排列 \(p\) 的 \(f_min(p)\) 与 \(f_max(p)\) 之和。
\(n \le 5000\)
Sol
不难想到一个简单的 \(\texttt{dp}\)，设 \(f_{i, j}\) 表示放了 \(i\) 个数，当前最大值的排名为 \(j\) 的权值贡献和，因此每加入一个数的贡献就是 \(f_{i, j} \times a_i\)。
将每一次最小值的贡献用转移表示出来，注意到事实上若同一个数转移了多次，那么当前放的数不会是之前的 \(a_i\)，因此需要乘上一个排列，表示选出前面的数的方案。
第一次新加入则不需要乘上这个贡献，前缀和优化转移即可。
标签：NOIP,min,max,20240821,YC327A,贡献,minmax,prod From： https://www.cnblogs.com/cxqghzj/p/18373056