https://ctp314.github.io/2019/08/05/50809102-NOIP%E6%A8%A1%E6%8B%9F%E9%A2%98/#more
a 给定程序，求程序地期望运行结果 考虑一个长度为 $n$ 地排列，其逆序对数地期望为 $\frac{\binom{n}{2}}{2}$，由此，不妨设 $f_n$ 为长度为 $n$ 的排列期望运行结果，则有 $$f_n\ =\ \frac{n(n-1)}{4}+\frac{1}{2^n}\sum_{i=0}^n\binom{n}{i}f_i$$
https://ctp314.github.io/2019/08/05/50809102-NOIP%E6%A8%A1%E6%8B%9F%E9%A2%98/#more
a 给定程序，求程序地期望运行结果 考虑一个长度为$n$ 地排列，其逆序对数地期望为 $\frac{\binom{n}{2}}{2}$ ，由此，不妨设 $f_n$ 为长度为 $n$ 的排列期望运行结果，则有 $$f_n\ =\ \frac{n(n-1)}{4}+\frac{1}{2^n}\sum_{i=0}^n\binom{n}{i}f_i$$