#4229. Inverse

题目描述

题解

考虑 $(i,j)$ 的贡献，于是设计dp： $f[i][j][k]$ 表示 $(i,j)$ 在 $k$ 轮之后 $p_i>p_j$ 的概率， $g[i][j][k]$ 表示 $p_i<p_j$的概率，其中 $i<j$ 。

考虑 $f$ 的转移，假设第 $k$ 轮翻转 $[l,r]$ ，设 $U=\frac{2}{n(n-1)}$ ，分类一下：
1. $l \in [1,i],r \in [i,j)$ ，贡献为 $U \times f[l+r-i][j][k-1]$ ；
2. $l \in (i,j],r \in [j,n]$ ，贡献为 $U \times f[i][l+r-j][k-1]$ ；
3. $l \in (i,j),r \in (i,j)$ ，贡献为 $U \times f[i][j][k-1]$ ；
4. $l \in [1,i],r \in [j,n]$ ，贡献为 $U \times g[l+r-i][l+r-j][k-1]$ 。

$g$ 的转移是类似的。

对于前两个来说，我们发现有一维是固定的，所以另一维做二次前缀和即可，对于第四个来说，我们发现它的差是固定的，所以对于差我们做二次前缀和即可，因此效率为 $O(n^2k)$

代码先咕着吧，好晚了明天再写

#4229. Inverse

原文：https://www.cnblogs.com/xjqxjq/p/12301711.html