yaoxi-std 的博客

$\text{开}\mathop{\text{卷}}\limits^{ju\check{a}n}\text{有益}$

0%

P4223 期望逆序对

发表于 更新于 分类于

P4223 期望逆序对

题面

题目链接

解法

期望乘上$\binom{n}{2}^k$后，就变成了求所有情况的逆序对数量的总和。

考虑计算贡献。假设枚举了两个位置$i$和$j$，其变换前的序列中对应的数字为$x$和$y$，那么经过$k$次变换，在这两个位置上的数字有$7$中可能的情况：

而这$7$种状态之间可以在$1$次变换之中相互转化，所以考虑矩阵快速幂。

先列出转移矩阵如下：

算出了每种情况的数量后，可以开始统计答案了。

考虑枚举右端点$a_j=y$，通过树状数组统计出$ia_j$的通过计算求出并计为$gt_0$，$gt_1$和$gt_2$。

  • $(x,y)$: $p_0 \times gt_0$
  • $(y,x)$: $p_1 \times lt_0$
  • $(x,t)$: $p_2 \times \frac{gt_2+lt_1}{n-2}$
  • $(y,t)$: $p_3 \times \frac{lt_0(i-2)+gt_0(n-i)}{n-2}$
  • $(t,x)$: $p_4 \times \frac{gt_1+lt_2}{n-2}$
  • $(t,y)$: $p_5 \times \frac{gt_0(i-2)+lt_0(n-i)}{n-2}$

$(t,t)$这种情况放在最后一起考虑，贡献为$p_6 \times \frac{1}{2}\binom{n}{2}$。

AC代码

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
149
/**
 * @file:           P4223.cpp
 * @author:         yaoxi-std
 * @url:            https://www.luogu.com.cn/problem/P4223
*/
// #pragma GCC optimize ("O2")
// #pragma GCC optimize ("Ofast", "inline", "-ffast-math")
// #pragma GCC target ("avx,sse2,sse3,sse4,mmx")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define resetIO(x) \
    freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout)
#define debug(fmt, ...) \
    fprintf(stderr, "[%s:%d] " fmt "\n", __FILE__, __LINE__, ##__VA_ARGS__)
template <class _Tp>
inline _Tp& read(_Tp& x) {
    bool sign = false;
    char ch = getchar();
    long double tmp = 1;
    for (; !isdigit(ch); ch = getchar())
        sign |= (ch == '-');
    for (x = 0; isdigit(ch); ch = getchar())
        x = x * 10 + (ch ^ 48);
    if (ch == '.')
        for (ch = getchar(); isdigit(ch); ch = getchar())
            tmp /= 10.0, x += tmp * (ch ^ 48);
    return sign ? (x = -x) : x;
}
template <class _Tp>
inline void write(_Tp x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar((x % 10) ^ 48);
}
const int MAXN = 5e5 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;
int add(int x, int y);
int binom2(int x);
enum MatrixType {
    XY, YX, XT, YT, TX, TY, TT
};
struct Matrix {
    int (*a)[7];
    Matrix() { a = new int[7][7] {}; }
    Matrix(int n) {
        a = new int[7][7] {
            { binom2(n - 2), 1, n - 2, 0, 0, n - 2, 0 },
            { 1, binom2(n - 2), 0, n - 2, n - 2, 0, 0 },
            { 1, 0, binom2(n - 2) + n - 3, 1, 1, 0, n - 3 },
            { 0, 1, 1, binom2(n - 2) + n - 3, 0, 1, n - 3 },
            { 0, 1, 1, 0, binom2(n - 2) + n - 3, 1, n - 3 },
            { 1, 0, 0, 1, 1, binom2(n - 2) + n - 3, n - 3 },
            { 0, 0, 1, 1, 1, 1, binom2(n) - 4 }
        };
        for (int i = 0; i < 7; ++i)
            for (int j = 0; j < 7; ++j)
                a[i][j] %= MOD;
    }
    int* operator[](int i) { return a[i]; }
    friend Matrix operator*(const Matrix& lhs, const Matrix& rhs) {
        Matrix ret;
        for (int i = 0; i < 7; ++i)
            for (int j = 0; j < 7; ++j)
                for (int k = 0; k < 7; ++k)
                    ret.a[i][j] = add(ret.a[i][j], lhs.a[i][k] * rhs.a[k][j] % MOD);
        return ret;
    }
};
struct BinaryIndexTree {
    int c[MAXN], n;
    void init(int m) { n = m; }
    void add(int x, int v) {
        for (int i = x; i <= n; i += (i & -i))
            c[i] = ::add(c[i], v);
    }
    int sum(int x) {
        int ret = 0;
        for (int i = x; i; i -= (i & -i))
            ret = ::add(ret, c[i]);
        return ret;
    }
};
int n, k, a[MAXN], p[7], lt[3], gt[3], sum[3];
BinaryIndexTree ltr[3];
inline int add(int x, int y) {
    x += y;
    return x >= MOD ? x - MOD : x;
}
inline int mul(int x, int y) {
    return x * y % MOD;
}
int binom2(int x) {
    return x * (x - 1) / 2 % MOD;
}
int qpow(int x, int y) {
    int ret = 1;
    for (; y; y >>= 1, x = x * x % MOD)
        if (y & 1)
            ret = ret * x % MOD;
    return ret;
}
Matrix qpow(Matrix x, int y) {
    Matrix ret;
    for (int i = 0; i < 7; ++i)
        ret.a[i][i] = 1;
    for (; y; y >>= 1, x = x * x)
        if (y & 1)
            ret = ret * x;
    return ret;
}
signed main() {
    read(n), read(k);
    for (int i = 1; i <= n; ++i)
        read(a[i]);
    Matrix base(n), ret;
    ret[0][XY] = 1;
    ret = ret * qpow(base, k);
    for (int i = 0; i < 7; ++i)
        p[i] = ret[0][i];
    ltr[0].init(n);
    ltr[1].init(n);
    ltr[2].init(n);
    int ans = 0, inv = qpow(n - 2, MOD - 2);
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < 3; ++j) {
            lt[j] = ltr[j].sum(a[i]);
            gt[j] = sum[j] - lt[j];
        }
        ans = add(ans, mul(p[0], gt[0]));
        ans = add(ans, mul(p[1], lt[0]));
        ans = add(ans, mul(p[2], add(mul(gt[2], inv), mul(lt[1], inv))));
        ans = add(ans, mul(p[3], add(mul(lt[0], mul(i - 2, inv)), mul(gt[0], mul(n - i, inv)))));
        ans = add(ans, mul(p[4], add(mul(gt[1], inv), mul(lt[2], inv))));
        ans = add(ans, mul(p[5], add(mul(gt[0], mul(i - 2, inv)), mul(lt[0], mul(n - i, inv)))));
        ltr[0].add(a[i], 1);
        ltr[1].add(a[i], i - 1);
        ltr[2].add(a[i], n - i - 1);
        sum[0] = add(sum[0], 1);
        sum[1] = add(sum[1], i - 1);
        sum[2] = add(sum[2], n - i - 1);
    }
    ans = add(ans, mul(p[6], mul(binom2(n), qpow(2, MOD - 2))));
    write(ans), putchar('\n');
    return 0;
}