题解 P4223 【期望逆序对】

· · 题解

目前这题的两篇题解一篇过于简略（至少对我这种菜鸡来说），一篇有一些错误（是我当时太菜了看不懂QAQ），所以在自己摸索出这题的做法后，在这里对第二篇题解做一些补充：

首先，期望数乘以 \tbinom{n}{2}^k 后，变为统计所有方案下的逆序对数量的计数问题。

然后，我们现在有一个排列 \{x_i\} ， 对于初始状态下的 x_A 和 x_B ，我们定义一个数对 (p,q) 表示这两个数最终的位置，由于除了 A,B 之外的任意位置对于 a_A,a_B 都是等价的，所以我们所有其它位置为 C，于是我们最后的位置对只有 7 种：(A,B),(B,A),(C,B),(B,C),(A,C),(C,A),(C,C) 。

尝试构造矩阵利用矩阵快速幂求出转移 k 次后出现这些情况的方案数，由于构造较为显然，这里不详细展开，具体矩阵如下（第 1 到 7 行、列分别对应 (A,B),(B,A),(C,B),(B,C),(A,C),(C,A),(C,C) 七个状态）：

\left| \begin{matrix} \tbinom{n-2}{2}&1&n-2&0&n-2&0&0\\ 1&\tbinom{n-2}{2}&0&n-2&0&n-2&0\\ 1&0&\tbinom{n-2}{2}+(n-3)&1&0&1&n-3\\ 0&1&1&\tbinom{n-2}{2}+(n-3)&1&0&n-3\\ 1&0&0&1&\tbinom{n-2}{2}+(n-3)&1&n-3\\ 0&1&1&0&1&\tbinom{n-2}{2}+(n-3)&n-3\\ 0&0&1&1&1&1&\tbinom{n-2}{2}+2(n-4)+1 \end{matrix} \right|

做完了矩阵快速幂之后，我们已经知道了这七种位置对所对应的方案数，接下来就是统计答案的折磨快乐时间：

设以上七种位置对的方案数分别为 p_0,p_1 \dots p_6，并令 a_B,fa_B,ga_B 表示初始状态下 B 前面的数中，比 x_B 小的数的个数，比 x_B 小的数（位置用 pos 表示）的 pos-1 的和以及比 x_B 小的数的位置的 n-pos-1 的和。同理处理出大于 x_B 意义下的数 b_B,fb_B,fb_B ，然后我们枚举每一个位置 B ，并考虑与它配对的位置在它前面的贡献和（式子中省略下标 B ）：

结束状态为 (A,B) 的贡献（后面直接省略为状态了QAQ）：p_0 * b

解释：对于所有大于 x_B 的数，在该结束状态下都有 1 的贡献。

(B,A)$ ：$p_1 * a

解释：对于所有小于 x_B 的数，在该结束状态下都有 1 的贡献。

(C,B)$ ：$p_2*(b\frac{(B-2)}{n-2}+a\frac{(n-B)}{n-2})

解释：该结束状态下，对于大于 x_B 的数，不是 x_B 的那一个数共有 B-2 个位置与 x_B 构成逆序对，而对于所有 C 类位置，落在上面的概率应该是相等的（显然），于是贡献即为 p_2 * b\frac{(B-2)}{n-2} ，同理分析小于 x_B 的数即可。

(B,C)$ ：$p_3*(a\frac{(B-2)}{n-2}+b\frac{(n-B)}{n-2})

解释：对于所有小于 x_B 的数， x_B 都有 B-2 个位置与它构成逆序对，于是分析与上题类似。

(A,C)$ ：$p_4*(\frac{gb}{n-2}+\frac{fa}{n-2})

解释：对于一个位置为 pos~(pos<B,x_{pos}<x_B) 的数，如果选择它与 x_B 配对，那么 x_B 共有 pos-1 个位置与它构成逆序对，然后用类似于情况 3 的分析，总贡献为 \displaystyle(\sum_{x_{pos}<x_B,pos<B}\frac{pos-1}{n-2})=\frac{fa_B}{n-2} ，同理分析大于 x_B 的数即可。

(C,A)$ ：$p_5*(\frac{fb}{n-2}+\frac{ga}{n-2})

解释：同上。

(C,C)$ ：该情况最后单独统计即可，答案为 $\frac{p_6*\tbinom{n}{2}}{2}

由于 a,b,fa,fb,ga,gb 可以用树状数组 O(n\log n) 地求出，所以总复杂度是 O(n\log n) 的，但有些卡常，注意 b,fb,gb 可以用 a,fa,ga 推出，然后可以减小一半常数，就能通过本题了。

代码：

#include<bits/stdc++.h>
#define lb(x) (x&(-x))
#define M(x) (now.dt[0][x])
using namespace std;
typedef long long ll;
const int mod=1e9+7,N=5e5+10;
ll inv2,n,k,nm[N],dt[2][N];
ll ans;
struct aa
{
    ll dt[10][10];
    aa operator *(const aa &b)const
    {
        aa res; memset(res.dt,0,sizeof(res.dt));
        for(int i=0;i<7;i++)
            for(int j=0;j<7;j++)
                for(int li=0;li<7;li++) res.dt[i][j]=(res.dt[i][j]+dt[i][li]*b.dt[li][j])%mod;
        return res;
    }
}mt,now;
int read()
{
    int res=0,fl=0; char a=getchar();
    while(a<'0'||a>'9') {if(a=='-') fl=1;a=getchar();}
    while(a>='0'&&a<='9') res=res*10+a-'0',a=getchar();
    return fl? -res:res;
}
ll ksm(ll di,ll mi) {ll res=1; for(;mi;mi>>=1,di=di*di%mod) if(mi&1) res=res*di%mod; return res;}
ll c2(ll x) {return x*(x-1)/2%mod;}
void add(ll fl,ll x,ll k) {for(;x<=n;x+=lb(x)) dt[fl][x]=(dt[fl][x]+k)%mod;}
ll query(ll fl,ll x) {ll res=0; for(;x;x-=lb(x)) res=(res+dt[fl][x])%mod; return res;}
int main()
{
    ll i,j,ff=0,gg=0;
    n=read(),k=read(),inv2=ksm(2,mod-2);
    for(i=1;i<=n;i++) nm[i]=read();
    mt=aa{{
    {c2(n-2),1,n-2,0,n-2,0,0},
    {1,c2(n-2),0,n-2,0,n-2,0},
    {1,0,(c2(n-2)+(n-3))%mod,1,0,1,n-3},
    {0,1,1,(c2(n-2)+(n-3))%mod,1,0,n-3},
    {1,0,0,1,(c2(n-2)+(n-3))%mod,1,n-3},
    {0,1,1,0,1,(c2(n-2)+(n-3))%mod,n-3},
    {0,0,1,1,1,1,(c2(n-2)+2*(n-4)+1)%mod}
    }},now.dt[0][0]=1;
    for(;k;k>>=1,mt=mt*mt) if(k&1) now=now*mt;
    for(i=1;i<=n;i++)
    {
        ll a=query(0,nm[i]),b=i-1-a,fa=query(1,nm[i]),fb=(ff-fa+mod)%mod,ga=((n-2)*a-fa)%mod,gb=(gg-ga+mod)%mod;
        ans=(ans+b*M(0)+a*M(1)+((b*(i-2)+a*(n-i))%mod*M(2)%mod+(a*(i-2)+b*(n-i))%mod*M(3)%mod+(gb+fa)*M(4)%mod+(ga+fb)*M(5)%mod)%mod*ksm(n-2,mod-2))%mod;
        add(0,nm[i],1),add(1,nm[i],i-1),ff=(ff+i-1)%mod,gg=(gg+n-i-1)%mod;
    }
    cout<<(ans+c2(n)*inv2%mod*M(6))%mod;
    return 0;
}