题目描述：
小C有一个 $1$ 到 $n$ 的排列 $P$，他会进行 $k$ 次操作，每次等概率选择一段连续区间(每次有 $frac{n(n+1)}{2}$ 种选择)，然后翻转这个区间。
小C想知道 $k$ 次操作后逆序对的期望个数，他觉得这实在是个一眼题，于是这个任务就交给你了。
为了避免精度误差，你只需要输出期望在模 $10^9 + 7$ 意义下的结果。
算法标签：前缀和套前缀和DP优化
思路：
$f[i][j][k]$ 表示 $i,j$ 这两个位置经过 $k$ 次操作，$ai>aj$ 的概率。
第一类：
(区间不覆盖 $i, j$ )
$$
f[i][j][k]+=sum_{r=1}^{rle i-1}sum_{l=1}^{lle r}f[l][r][k-1] imes P
$$
$$
f[i][j][k]+=sum_{l=j+1}^{lle n}sum_{r=l}^{rle n}f[l][r][k-1] imes P
$$
总结起来就是：
$$
f[i][j][k]+=f[i][j][k-1] imes P imes (frac{i imes (i-1)}{2}+frac{(n-j) imes (n-j+1)}{2}+frac{(j-i) imes (j-i-1)}{2})
$$
第二类：
(区间只覆盖 $i,j$ 中的一个)
$$
f[i][j][k]+=sum_{l=1}^{lle i}sum_{r=i}^{rle j-1}f[l+r-i][j][k-1] imes P
$$
当发现 $j$ 是固定的所以对其前缀和
$$
f[i][j][k]+=sum_{l=1}^{lle i}（s1[l-i+j-1][j]-s1[l-1][j]） imes P
$$
发现第二位仍然是一样的，再进行一次前缀和
$$
f[i][j][k]+=(s2[j-1][j]-s2[j-i-1][j]-s2[i-1][j]) imes P
$$
$$
f[j][j][k]+=sum_{l=i+1}^{lle r}sum_{r=j}^{r<=n}f[i][l+r-j][k-1] imes P()
$$
这个式子同上用两次前缀和化简。
第三类：
（区间同时覆盖了 $i, j$ ，意味着两者逆序对的方案数发生变化）
$$
f[i][j][k]+=sum_{l=1}^{lle i}sum_{r=j}^{rle n}(1-f[l+r-i][l+r-j][k-1]) imes P
$$
这类的化简有点不同，发现每一项都在变化，但是发现第一项和第二项的距离不变。
所以考虑令 $g1[i][j]$ 表示f的距离为 $i$ ，第一项为 $j$ 的前缀和。
$$
f[i][j][k]+=P imes (n-j+1) imes i-sum_{l=1}^{lle i}(g1[l-i+n][i-j]-g1[l-i+j-1][i-j])
$$
然后就是类似之前的前缀和
$$
f[i][j][k]+=P imes (n-j+1) imes i-g2[n+i-j][j-i]+g2[n-j][j-i]+g2[i-1][j-i]
$$
真可怕......
以下代码：
#include<bits/stdc++.h> #define il inline #define LL long long #define _(d) while(d(isdigit(ch=getchar()))) using namespace std; const int N=505,p=1e9+7; int n,k,a[N],f[N][N],A[N][N],B[N][N],C[N][N],inv; il int read(){ int x,f=1;char ch; _(!)ch=='-'?f=-1:f;x=ch^48; _()x=(x<<1)+(x<<3)+(ch^48); return f*x; } il int mu(int x,int y){ return (x+y>=p)?x+y-p:x+y; } il int ksm(LL a,int y){ LL b=1; while(y){ if(y&1)b=b*a%p; a=a*a%p;y>>=1; } return b; } int main() { n=read();k=read();inv=ksm(n*(n+1)/2,p-2); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++)f[i][j]=a[i]>a[j]; while(k--){ for(int j=1;j<=n;j++){ for(int i=1;i<j;i++)A[i][j]=mu(A[i-1][j],f[i][j]); for(int i=1;i<j;i++)A[i][j]=mu(A[i-1][j],A[i][j]); } for(int i=n;i;i--){ for(int j=n;j>i;j--)B[i][j]=mu(f[i][j],B[i][j+1]); for(int j=n;j>i;j--)B[i][j]=mu(B[i][j],B[i][j+1]); } for(int j=0;j<n;j++){ for(int i=1;i<=n-j;i++)C[i][j]=mu(C[i-1][j],f[i][i+j]); for(int i=1;i<=n-j;i++)C[i][j]=mu(C[i][j],C[i-1][j]); } for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ f[i][j]=1ll*f[i][j]*mu(1ll*i*(i-1)/2%p,mu(1ll*(n-j)*(n-j+1)/2%p,1ll*(j-i-1)*(j-i)/2%p))%p; f[i][j]=mu(f[i][j],mu(A[j-1][j],p-mu(A[j-i-1][j],A[i-1][j]))); f[i][j]=mu(f[i][j],mu(B[i][i+1],p-mu(B[i][j+1],B[i][n+2-j+i]))); f[i][j]=mu(f[i][j],mu(1ll*i*(n-j+1)%p,mu(C[n-j][j-i],mu(C[i-1][j-i],p-C[n+i-j][j-i])))); f[i][j]=1ll*f[i][j]*inv%p; } } } int ans=0; for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)ans=mu(ans,f[i][j]); printf("%d ",ans); return 0; }