[ARC176D] Swap Permutation
Hanghang
·
·
题解
[ARC176D] Swap Permutation
介绍一种这类题目通用的解法。
对于任意两个位置 A,B，其他的值最终到达这里的概率都是相等的，不妨设它为 C，那么最终对应位置的情况只有 7 种：(A,B),(B,A),(C,B),(B,C),(A,C),(C,A),(C,C)。
考虑对换两个数之后变化的方案数，构造矩阵：
M=\begin{bmatrix}
\binom{n-2}{2} & 1 & n-2 & 0 & n-2 & 0 & 0\\
1 & \binom{n-2}{2} & 0 & n-2 & 0 & n-2 & 0\\
1 & 0 & \binom{n-2}{2}+n-3 & 1 & 0 & 1 & n-3 \\
0 & 1 & 1 & \binom{n-2}{2}+n-3 & 1 & 0 & n-3\\
1 & 0 & 0 & 1 &\binom{n-2}{2}+n-3 & 1 & n-3\\
0 & 1 & 1 & 0 & 1 &\binom{n-2}{2}+n-3 & n-3\\
0 & 0 & 1 & 1 & 1 & 1 &\binom{n-2}{2}+2(n-4)+1
\end{bmatrix}
其中矩阵第 i 行第 j 列恰好对应着从第 i 种情况通过一次对换走到第 j 种情况的方案数。
那么：
e\times M^k=f
可以使用矩阵快速幂在 $O(T^3\log m)$ 的时间求得 $f$，$T$ 为矩阵大小 $7$，由于 $k$ 一般情况下不可能开得非常大（超过 $10^{18}$ 级别），所以这部分的计算时间往往可以忽略不记。
现在考虑每种情况对应的贡献。
在此题中，我们只需要考虑相邻点对的贡献，一共只有 $n$ 对，直接一个个处理即可（其他的一些题目不一定只有 $n$ 对，方法往往是枚举右边的值然后处理所有的贡献）。
设当前在处理 $(i,i+1)$ 这一点对，值分别为 $a_i,a_{i+1}$。
$(A,B),(B,A)$ 的贡献分别为：
$$
f_1\times |a_i-a_{i+1}|\\f_2\times |a_i-a_{i+1}|
$$
设 $sum_x=\displaystyle\sum_{i=1}^{n}|i-x|$。
$(C,B),(B,C)$ 的贡献分别为：
$$
\dfrac{f_3\times (sum_{a_{i+1}}-|a_i-a_{i+1}|)}{n-2}\\\dfrac{f_4\times (sum_{a_{i+1}}-|a_i-a_{i+1}|)}{n-2}
$$
即点对中的一个值是固定的，另一个值可以是除了 $A$ 中的所有数，每个数都是等概率的，所有直接求和再除以 $n-2$ 即可。
$(A,C),(C,A)$ 的贡献同理，分别为：
$$
\dfrac{f_5\times (sum_{a_{i}}-|a_i-a_{i+1}|)}{n-2}\\\dfrac{f_6\times (sum_{a_{i}}-|a_i-a_{i+1}|)}{n-2}
$$
最后考虑 $(C,C)$ 的贡献，还是因为等概率，贡献应是两个数不为 $A,B$ 的所有可能求和除以 $(n-2)(n-3)$。
设 $sx=\displaystyle\sum_{i=1}^{n}sum_i$，那么贡献为：
$$
\dfrac{f_7\times (sx-2(sum_{a_i}-sum_{a_{i+1}}-|a_i-a_{i+1}|)}{(n-2)(n-3)}
$$
把所有贡献加起来即为答案。
复杂度 $O(n+T^3\log m)$。
类似题目：[P4223 期望逆序对](https://www.luogu.com.cn/problem/P4223)（本题思路借鉴了 $\text{Yukikaze\_}$ 的题解）。
代码（$f$ 数组的下标有一些小小的改变）：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e5+3,H=998244353;
ll Ksm(ll x,ll y)
{
ll s=1;
for(ll i=1;i<=y;i<<=1,x=x*x%H)if(i&y)s=s*x%H;
return s;
}
struct Mat
{
ll mat[7][7];
void Clear(){memset(mat,0,sizeof(mat));}
friend Mat operator *(Mat A,Mat B)
{
Mat C;C.Clear();
for(int i=0;i<=6;i++)for(int j=0;j<=6;j++)for(int k=0;k<=6;k++)
C.mat[i][j]=(C.mat[i][j]+A.mat[i][k]*B.mat[k][j])%H;
return C;
}
}bas,res;
ll n,m,a[N],sum[N];
ll C2(ll x){return x*(x-1)/2%H;}
ll S(ll l,ll r){return l>r?0:(l+r)*(r-l+1)/2;}
void Init()
{
res.mat[0][0]=1;
bas=(Mat){{
{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))%H,1,0,1,n-3},
{0,1,1,(C2(n-2)+(n-3))%H,1,0,n-3},
{1,0,0,1,(C2(n-2)+(n-3))%H,1,n-3},
{0,1,1,0,1,(C2(n-2)+(n-3))%H,n-3},
{0,0,1,1,1,1,(C2(n-2)+2*(n-4)+1)%H}
}};
}
int main()
{
cin>>n>>m;Init();ll sx=0;
for(int i=1;i<=n;i++)cin>>a[i];
for(ll i=1;i<=n;i++)sum[i]=((i-1)*i-S(1,i-1)+S(i+1,n)-(n-i)*i)%H,sx=(sx+sum[i])%H;
for(ll i=1;i<=m;i<<=1,bas=bas*bas)if(i&m)res=res*bas;
ll *f=res.mat[0],ans=0,ivn2=Ksm(n-2,H-2),ivn3=Ksm((n-2)*(n-3)%H,H-2);
for(int i=1;i<n;i++)
{
ll dt=abs(a[i+1]-a[i]),ka=sum[a[i]],kb=sum[a[i+1]];
ans=(ans+(f[0]+f[1])*dt)%H;
ans=(ans+(f[2]+f[3])*(kb-dt+H)%H*ivn2)%H;
ans=(ans+(f[4]+f[5])*(ka-dt+H)%H*ivn2)%H;
ans=(ans+f[6]*(sx+(-ka-kb+dt+2*H)*2)%H*ivn3)%H;
}
cout<<ans;
}
```