自动搬运

查看原文

来自洛谷，原作者为

	Yukikaze_ **

搬运于2025-08-24 21:57:50，当前版本为作者最后更新于2020-09-15 15:40:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

目前这题的两篇题解一篇过于简略（至少对我这种菜鸡来说），一篇有一些错误（是我当时太菜了看不懂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;
}