解题报告

其实不用管期望……只要算出总贡献然后最后除以 $(n^2)^k​$ 就行了（Manchery：期望就是层壳），不过也可以利用期望的线性性把期望转成概率。

算贡献的时候如果真的按照题目中给的方法去算，是不可能避免掉指数级状态的，所以我们要想办法把贡献拆掉（比如拆到数值上或者位置上），从而变成比较简单的形式。考虑一个元素 $y$ 在 $x$ 处有贡献，需要满足 $[1,x-1]$ 均没有 $>y$ 的元素，均没有这个条件已经很强了，所以我们可以计算每个元素在每个位置时的贡献！

先枚举 $x,y$ ，然后根据上述性质，我们可以定义 $f_{i,j,s}$ 表示第 $i$ 轮交换后，$[1,x-1]$ 中有 $j$ 个比 $y$ 大以及当前状态 $s$ ，观察一下我们发现只需要知道 $y$ 目前在哪里以及目前 $x$ 上的数是否 $>y$ 就可以进行转移了，又因为最后只需要 $y$ 在 $x$ 上这一个状态，所以可以把 $s$ 分五类：

1. $y$ 在 $x$ 上。
2. $y$ 在 $x$ 左边，$x$ 上的数 $>y$ 。
3. $y$ 在 $x$ 右边，$x$ 上的数 $>y$ 。
4. $y$ 在 $x$ 左边，$x$ 上的数 $<y$ 。
5. $y$ 在 $x$ 右边，$x$ 上的数 $<y$ 。

恭喜你，你马上就要做完了，只需要讨论40种情况（我恨出题人）。

示例程序

因为转移有巨大常数所以需要调整好循环上下界。

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int maxn=100,maxk=80,MOD=1e9+7;

int n,K,a[maxn+5],pos[maxn+5],p[maxn*maxn+5],f[maxk+5][maxn+5][6],ans;

inline int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;}
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline int DP(int x,int y){
    if (n-x<n-y) return 0;int cnt=0;for (int i=1;i<x;i++) cnt+=a[i]>y;
    for (int i=0;i<=K;i++) for (int j=0;j<x&&j<=n-y;j++) for (int k=1;k<=5;k++) f[i][j][k]=0;
    if (pos[y]<x) a[x]>y?f[0][cnt][2]=1:f[0][cnt][4]=1;
    if (pos[y]==x) f[0][cnt][1]=1;
    if (pos[y]>x) a[x]>y?f[0][cnt][3]=1:f[0][cnt][5]=1;
    for (int i=0;i<K;i++)
        for (int j=0;j<x&&j<=n-y;j++){
            //f[i][j][1]
            int LB=j,LS=x-1-LB,RB=n-y-LB,RS=n-x-RB,F=f[i][j][1];
            if (LB>=0&&LS>=0&&RB>=0&&RS>=0&&F){
                AMOD(f[i+1][j][1],(LL)F*p[1+(x-1)*(x-1)+(n-x)*(n-x)+2*LB*RB+2*LS*RS]%MOD);
                if (j) AMOD(f[i+1][j-1][1],(LL)F*p[2*LB*RS]%MOD);
                AMOD(f[i+1][j+1][1],(LL)F*p[2*LS*RB]%MOD);
                if (j) AMOD(f[i+1][j-1][2],(LL)F*p[2*LB]%MOD);
                AMOD(f[i+1][j][3],(LL)F*p[2*RB]%MOD);
                AMOD(f[i+1][j][4],(LL)F*p[2*LS]%MOD);
                AMOD(f[i+1][j][5],(LL)F*p[2*RS]%MOD);
            }
            //f[i][j][2]
            LB=j;LS=x-1-1-LB;RB=n-y-(LB+1);RS=n-x-RB;F=f[i][j][2];
            if (LB>=0&&LS>=0&&RB>=0&&RS>=0&&F){
                AMOD(f[i+1][j][2],(LL)F*p[1+(x-1)*(x-1)+(n-x)*(n-x)+2*LB*RB+2*LS*RS+2*LB+2*RB]%MOD);
                if (j) AMOD(f[i+1][j-1][2],(LL)F*p[2*LB*RS]%MOD);
                AMOD(f[i+1][j+1][2],(LL)F*p[2*LS*RB]%MOD);
                AMOD(f[i+1][j+1][1],(LL)F*p[2]%MOD);
                AMOD(f[i+1][j][3],(LL)F*p[2*RS]%MOD);
                AMOD(f[i+1][j+1][3],(LL)F*p[2*RB]%MOD);
                AMOD(f[i+1][j+1][4],(LL)F*p[2*LS]%MOD);
                AMOD(f[i+1][j][4],(LL)F*p[2*RS]%MOD);
            }
            //f[i][j][3]
            LB=j;LS=x-1-LB;RB=n-y-(LB+1);RS=n-x-1-RB;F=f[i][j][3];
            if (LB>=0&&LS>=0&&RB>=0&&RS>=0&&F){
                AMOD(f[i+1][j][3],(LL)F*p[1+(x-1)*(x-1)+(n-x)*(n-x)+2*LB*RB+2*LS*RS+2*LB+2*RB]%MOD);
                if (j) AMOD(f[i+1][j-1][3],(LL)F*p[2*LB*RS]%MOD);
                AMOD(f[i+1][j+1][3],(LL)F*p[2*LS*RB]%MOD);
                AMOD(f[i+1][j][1],(LL)F*p[2]%MOD);
                AMOD(f[i+1][j][2],(LL)F*p[2*LS]%MOD);
                if (j) AMOD(f[i+1][j-1][2],(LL)F*p[2*LB]%MOD);
                AMOD(f[i+1][j+1][5],(LL)F*p[2*LS]%MOD);
                AMOD(f[i+1][j][5],(LL)F*p[2*RS]%MOD);
            }
            //f[i][j][4]
            LB=j;LS=x-1-1-LB;RB=n-y-LB;RS=n-x-RB;F=f[i][j][4];
            if (LB>=0&&LS>=0&&RB>=0&&RS>=0&&F){
                AMOD(f[i+1][j][4],(LL)F*p[1+(x-1)*(x-1)+(n-x)*(n-x)+2*LB*RB+2*LS*RS+2*LS+2*RS]%MOD);
                if (j) AMOD(f[i+1][j-1][4],(LL)F*p[2*LB*RS]%MOD);
                AMOD(f[i+1][j+1][4],(LL)F*p[2*LS*RB]%MOD);
                AMOD(f[i+1][j][1],(LL)F*p[2]%MOD);
                if (j) AMOD(f[i+1][j-1][2],(LL)F*p[2*LB]%MOD);
                AMOD(f[i+1][j][2],(LL)F*p[2*RB]%MOD);
                AMOD(f[i+1][j][5],(LL)F*p[2*RS]%MOD);
                AMOD(f[i+1][j+1][5],(LL)F*p[2*RB]%MOD);
            }
            //f[i][j][5]
            LB=j;LS=x-1-LB;RB=n-y-LB;RS=n-x-1-RB;F=f[i][j][5];
            if (LB>=0&&LS>=0&&RB>=0&&RS>=0&&F){
                AMOD(f[i+1][j][5],(LL)F*p[1+(x-1)*(x-1)+(n-x)*(n-x)+2*LB*RB+2*LS*RS+2*LS+2*RS]%MOD);
                if (j) AMOD(f[i+1][j-1][5],(LL)F*p[2*LB*RS]%MOD);
                AMOD(f[i+1][j+1][5],(LL)F*p[2*LS*RB]%MOD);
                AMOD(f[i+1][j][1],(LL)F*p[2]%MOD);
                AMOD(f[i+1][j-1][3],(LL)F*p[2*LB]%MOD);
                AMOD(f[i+1][j][3],(LL)F*p[2*RB]%MOD);
                AMOD(f[i+1][j][4],(LL)F*p[2*LS]%MOD);
                if (j) AMOD(f[i+1][j-1][4],(LL)F*p[2*LB]%MOD);
            }
        }
    return f[K][0][1];
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&K);for (int i=1;i<=n;i++) scanf("%d",&a[i]),pos[a[i]]=i;
    for (int i=1,INV=Pow(n*n,MOD-2);i<=n*n;i++) p[i]=(LL)i*INV%MOD;
    for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) AMOD(ans,DP(i,j));
    return printf("%d\n",ans),0;
}