给出一个nn 的排列，求 kk 次随机交换之后，所有方案的逆序对的和

n≤500000,k≤109n\le 500000,k\le 10^9

神仙题

Brief Analysis

总体思路是考虑每对数字对答案的贡献

每对ai,aja_i,a_j在末状态的时候，所处位置有三种可能的情况， ii，jj ，或其他位置

不难发现，这个数对最后的位置情况只有77种，那么写出矩阵后可以用矩阵快速幂算出最后每种状态的方案数

最后再用BIT统计答案即可

Whole Solution

对于每对数，考虑计算它们在最终状态对答案的贡献

设初始状态下，当前考虑ii和jj这两个位置上的数，设它们分别为 、

因为对于这两个数来说其他所有位置的数都是等价的，于是可以都看成CC（注意，因为实际上CC是不同的，所以计算方案时也要看作不同，这里只是因为它对当前数对的贡献都没有影响，于是方便表示都记为CC）

即

那么最终状态下(i,j)(i,j)位置所对应的值无非就是(A,B),(A,C),(B,A),(B,C),(C,A),(C,B),(C,C)(A,B),(A,C), (B,A), (B,C), (C, A), (C, B), (C, C)这七种情况

显然，计算的过程可以用矩阵快速幂优化，考虑转移一步时的转移矩阵如下：

（矩阵的第ii行jj列表示从第ii个状态转移到第jj个状态所需要乘上的值）

[(n−22)n−2100n−201(n−22)+n−30110n−310(n−22)n−2n−200011(n−22)+n−301n−30110(n−22)+n−31n−310011(n−22)+n−3n−3010111(n−22)+2(n−4)+1] \begin{bmatrix} \binom{n-2}{2}& n-2 & 1 & 0 & 0 & n-2 & 0\\ 1& \binom{n-2}{2}+n-3 & 0 & 1 & 1 & 0 &n-3 \\ 1& 0 & \binom{n-2}{2} & n-2 & n-2 & 0 &0 \\ 0& 1 & 1 & \binom{n-2}{2}+n-3 & 0 & 1 & n-3\\ 0 & 1 & 1 & 0 & \binom{n-2}{2}+n-3 & 1 & n-3\\ 1 & 0 & 0 & 1 & 1 & \binom{n-2}{2}+n-3 & n-3\\ 0& 1 & 0 & 1 & 1 &1 & \binom{n-2}{2}+2(n-4)+1 \end{bmatrix}

最终矩阵的第一行从00到66分别表示状态为(A,B),(A,C),(B,A),(B,C),(C,A),(C,B),(C,C)(A,B),(A,C), (B,A), (B,C), (C, A), (C, B), (C, C)的答案

但是，如果我们直接枚举A,BA,B的话复杂度是O(n2)O(n^2)的，显然过不了

注意到，在确定AA和BB中任意一个后，另外一个的具体的值并不重要，只需要知道它们的大小关系

不妨确定BB，利用树状数组统计所有AA的贡献

假设当前考虑到第ii个数，它的值为B(ai)B(a_i)，用树状数组维护几个值：

  • numanum_a：原排列中位置在BB之前，且权值比BB小的数的个数

  • faf_a：原排列中位置在BB之前，且权值比BB小的数，它所有前面的位置的和

    ​ 这个好拗口啊，用式子表示就是fa=∑j<i,aj<Bj−1f_a=\sum_{j < i, a_j<B}j-1

  • gag_a：原排列中位置在BB之前，且权值比BB小的数，它所有后面的位置（不包括ii）的和

    ​ 同样，用式子表示是ga∑j<i,aj<Bn−j−1g_a\sum_{j<i, a_j < B}n-j-1（要再减一是因为要去掉ii这个位置）

numb,fb,gbnum_b,f_b,g_b为位置在BB之前，权值比BB大的值，定义与上面类似

设ans[i]∣i∈[0,6]ans[i] | i\in[0,6]表示之前处理出来的矩阵中第00行第ii列的值（即从一开始(A,B)(A,B)状态转移到第ii个状态所需要乘上的值）

那么统计最终答案的方法：

(A,B):numb∗ans[0](A,B):num_b * ans[0]

在BB前面，满足A>BA>B的AA的个数

(A,C):(fa+gb)∗ans[1]∗1n−2(A,C): (f_a + g_b)*ans[1] * \frac{1}{n-2}

因为最终的BB的位置不确定，分两种情况考虑

若最终BB在AA前面，那么要满足B>AB>A

若最终BB在AA后面，那么要满足A>BA>B，且此时BB不能放在ii的位置，这就是为什么前面计算 、 的时候需要−1-1

顺便在这里解释一下所有只要带 的就要除 的原因是，在做矩阵快速幂的时候我们是把所有的等价 的总数都算进去了，但此处需要计算某一个具体的 的影响，所以要把方案数除以

(B,A):numa∗ans[2](B,A):num_a * ans[2]

同(A,B)(A,B)

(B,C):(fb+ga)∗ans[3]∗1n−2(B,C):(f_b + g_a) * ans[3] * \frac{1}{n-2}

同(A,C)(A, C)

(C,A):(numa∗(i−2)+numb∗(n−i))∗ans[4]∗1n−2(C, A): \Big(num_a * (i - 2) + num_b * (n -i)\Big)*ans[4] * \frac{1}{n-2}

大致思想同(A,C)(A,C)，考虑AA和BB的位置关系

(C,B):(numb∗(i−2)+numa∗(n−i))∗ans[5]∗1n−2(C,B): \Big(num_b * (i-2) + num_a * (n-i)\Big)*ans[5] * \frac{1}{n-2}

同(C,A)(C,A)

最后还剩一种(C,C)(C,C)，我们可以把它提出来，对所有的CC一起算

(C,C):(n2)∗12∗ans[6](C,C): \binom{n}{2}*\frac{1}{2}*ans[6]

对于这些CC,总共有(n2)\binom{n}{2} 种组合，每两种组合只会产生一个逆序对，要么大的在前面要么小的在前面

总复杂度O(nlogn+73logk)O(n\log n + 7^3\log k)

Something

在最后一步算答案的时候，不难观察样例和打表发现，ans[]ans[]中有几对值是相同的

目前网上的所有题解我感觉对ans[]ans[]的解释都有点问题，不过因为恰好相同所以答案是正确的

但我按自己的想法推出来的东西写完之后是能过的

不知道是不是我自己太菜还没想清楚啊。。。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }

inline void proc_status()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) <<endl;
}

template <typename T> T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

const int Maxn = 5e5 + 10, Maxk = 10, Mod = 1e9 + 7;

int N, K, A[Maxn], fac[Maxn], ifac[Maxn];

inline void Add (int &a, int b) { a += b; if (a >= Mod) a -= Mod; }

inline int Pow (int a, int b)
{
	int ans = 1;
	for (; b; a = 1ll * a * a % Mod, b >>= 1) if (b & 1) ans = 1ll * ans * a % Mod;
	return ans;
}

inline int C (int n, int m) {return 1ll * fac[n] * ifac[m] % Mod * ifac[n - m] % Mod; } 

struct BIT
{
#define lowbit(x) (x & (-x))
	int sum[Maxn];
	inline void add (int x, int val) { for (; x <= N; x += lowbit(x)) Add (sum[x], val); }
	inline int query (int x) { int ans = 0; for (; x; x -= lowbit(x)) Add (ans, sum[x]); return ans; }
} T[3];

struct Matrix
{
	int A[Maxk][Maxk];

	inline void init () 
	{ 
		memset(A, 0, sizeof A); 
		for (int i = 0; i <= 6; ++i) A[i][i] = 1;
	}

	inline void _init ()
	{
		for (int i = 0; i <= 6; ++i) A[i][i] = C(N - 2, 2);
		A[0][1] = A[0][5] = N - 2, A[0][2] = 1;
		A[1][0] = A[1][3] = A[1][4] = 1, Add (A[1][1], N - 3), A[1][6] = N - 3;
		A[2][0] = 1, A[2][3] = A[2][4] = N - 2;
		A[3][1] = A[3][2] = A[3][5] = 1, Add (A[3][3], N - 3), A[3][6] = N - 3;
		A[4][1] = A[4][2] = A[4][5] = 1, Add (A[4][4], N - 3), A[4][6] = N - 3;
		A[5][0] = A[5][3] = A[5][4] = 1, Add (A[5][5], N - 3), A[5][6] = N - 3;
		A[6][1] = A[6][3] = A[6][4] = A[6][5] = 1, Add (A[6][6], 2ll * (N - 4) % Mod + 1);
	}

	inline Matrix operator * (const Matrix &rhs) const
	{
		Matrix c;
		for (int i = 0; i <= 6; ++i)
			for (int j = 0; j <= 6; ++j)
			{
				c.A[i][j] = 0;
				for (int k = 0; k <= 6; ++k)
					Add (c.A[i][j], 1ll * A[i][k] * rhs.A[k][j] % Mod);
			}
		return c;
	}

} trans, sum;

inline void Init ()
{
	fac[0] = 1;
	for (int i = 1; i <= N; ++i) fac[i] = 1ll * fac[i - 1] * i % Mod;
	ifac[N] = Pow(fac[N], Mod - 2);
	for (int i = N - 1; i >= 0; --i) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % Mod;
	sum.init(), trans._init();
}

int Ans[Maxk];

inline void Solve ()
{
	Init();
	for (int i = K; i; trans = trans * trans, i >>= 1)
	{
		if (i & 1) sum = sum * trans;
	}
	for (int i = 0; i <= 6; ++i) Ans[i] = sum.A[0][i];

	int f_sum = 0, g_sum = 0, ans = 0;
	int inv = Pow(N - 2, Mod - 2);
	for (int i = 1; i <= N; ++i)
	{
		int num_a = T[0].query (A[i]), f_a = T[1].query (A[i]), g_a = T[2].query (A[i]);
		int num_b = i - 1 - num_a, f_b = f_sum - f_a, g_b = g_sum - g_a;

		Add (ans, 1ll * num_b * Ans[0] % Mod);
		Add (ans, 1ll * (f_a + g_b) % Mod * Ans[1] % Mod * inv % Mod);
		Add (ans, 1ll * num_a * Ans[2] % Mod);
		Add (ans, 1ll * (f_b + g_a) % Mod * Ans[3] % Mod * inv % Mod);
		Add (ans, 1ll * (1ll * num_a * (i - 2) % Mod + 1ll * num_b * (N - i) % Mod) % Mod * Ans[4] % Mod * inv % Mod);
		Add (ans, 1ll * (1ll * num_b * (i - 2) % Mod + 1ll * num_a * (N - i) % Mod) % Mod * Ans[5] % Mod * inv % Mod);

		T[0].add (A[i], 1), T[1].add (A[i], i - 1), T[2].add (A[i], N - i - 1);
		Add (f_sum, i - 1), Add (g_sum, N - i - 1);
	}
	Add (ans, 1ll * C(N, 2) * Pow(2, Mod - 2) % Mod * Ans[6] % Mod);
	cout<<ans<<endl;
}

inline void Input ()
{
	N = read<int>(), K = read<int>();
	for (int i = 1; i <= N; ++i) A[i] = read<int>();
}

int main()
{
#ifdef hk_cnyali
	freopen("A.in", "r", stdin);
	freopen("A.out", "w", stdout);
#endif
	Input();
	Solve();
	return 0;
}