题解：P4223 期望逆序对

· · 题解

模拟赛 T4 弱化版，拼尽全力只能写出暴力 DP /ll。

下面，我们给出一个基于 DP 优化的，不需要讨论 7 种情况的做法。

记 f_{i,x,y} 为进行 i 轮操作后，a_x>a_y 的概率，答案即 \sum f_{k,x,y}。考虑在一轮中，x,y 的变化：

我们不妨在最后再让 f_{i,x,y} 乘上一个概率系数 \frac{2}{n(n-1)} 来让式子更自然。上面的转移是省略了系数的结果。

直接做为 O(kn^3)，对第 2&3 条转移记录一下行列和就是 O(kn^2) 了。可以获得 50 分。

:::::info[50pts 代码]

const int N = 505;
int n, k, a[N];
mint f[2][N][N], r[N], c[N];

void _main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= n; j++) f[0][i][j] = a[i] > a[j];
    const mint p = ~mint(n) * ~mint(n - 1) * 2, i2 = ~mint(2);
    for (int T = 1, st = 1; T <= k; T++, st ^= 1) { 
        for (int i = 1; i <= n; i++) r[i] = accumulate(f[st ^ 1][i] + 1, f[st ^ 1][i] + n + 1, mint(0));
        for (int j = 1; j <= n; j++) {
            c[j] = 0;
            for (int i = 1; i <= n; i++) c[j] += f[st ^ 1][i][j];
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) continue;
                f[st][i][j] = f[st ^ 1][i][j] * (n - 2) * (n - 3) * i2;  
                f[st][i][j] += r[i] - f[st ^ 1][i][j];
                f[st][i][j] += c[j] - f[st ^ 1][i][j];
                f[st][i][j] += f[st ^ 1][j][i];
                f[st][i][j] *= p;
            }
        }
    }
    mint res = 0;
    for (int i = 1; i <= n; i++) 
        for (int j = i + 1; j <= n; j++) res += f[k & 1][i][j];
    cout << res * (~p).pow(k);
}

:::::

以上是赛时会了的。以下是赛后问 Gemini 会的。

记 p=\frac{2}{n(n-1)}。整理一下转移式：

\begin{aligned} f_{i,x,y}&=p\left(\left(C_{n-2}^2-3\right)f_{i-1,x,y} +r_{i-1,x}+c_{i-1,y}+1\right)\\ r_{i,x}&=\sum_{y \ne x} f_{i,x,y}\\ c_{i,y}&=\sum_{x \ne y} f_{i,x,y} \end{aligned}

我们来观察一下性质：

性质 1 当 x \ne y 时，恒有 f_{i,x,y}+f_{i,y,x}=1。

性质 2 c_{i,y}=n-1-r_{i,y}。

:::::success[性质 2 的证明] 将性质 1 代入 c 的定义式：

\begin{aligned} c_{i,y}&=\sum_{x \ne y} f_{i,x,y}\\ &=\sum_{x \ne y} (1-f_{i,y,x})\\ &=n-1-\sum_{x \ne y} f_{i,y,x}\\ &=n-1-r_{i,y} \end{aligned}

:::::

性质 3 \sum\limits_{x' \ne x} r_{i,x'}=C_n^2-r_{i,x}。

:::::success[性质 3 的证明] 根据性质 1，在矩阵 f_i 中，非对角线的元素和为 C_n^2。

考虑 r 的定义即有 \sum \limits_{x}r_{i,x}=C_n^2。 :::::

根据性质 2，我们只需计算 r 即可实现加速转移的目的。接下来，将 f 的转移代入 r：

\begin{aligned} r_{i,x}&=\sum_{y \ne x} f_{i,x,y}\\ &=p\sum_{y \ne x}\left(\left(C_{n-2}^2-3\right)f_{i-1,x,y} +r_{i-1,x}+c_{i-1,y}+1\right)\\ &=p\left(\sum_{y \ne x}\left(C_{n-2}^2-3\right)+\sum_{y \ne x}r_{i-1,x}+\sum_{y \ne x}c_{i-1,y}+\sum_{y \ne x} 1\right)\\ &=p\left((C_{n-2}^2-3) r_{i-1,x} +(n-1)r_{i-1,x}+\sum_{y \ne x}(n-1-r_{i,x})+n-1\right)\\ &=p\left((C_{n-2}^2-3) r_{i-1,x} +(n-1)r_{i-1,x}+(n-1)^2-(C_n^2-r_{i-1,x})+n-1\right)\\ &=p\left(\dfrac{n(n-3)}{2}r_{i-1,x}+C_n^2\right)\\ &=\dfrac{n-3}{n-1}r_{i-1,x}+1 \end{aligned}

我们发现，r 和初始排列以及 f 的值无关！

解一阶线性递推得

r_{i,x}=\dfrac{n-1}{2}+\left(\dfrac{n-3}{n-1}\right)^i \left(r_{0,x}-\dfrac{n-1}{2}\right)

:::::success[怎么解] 记 \alpha=\frac{n-3}{n-1}。假定数列收敛于常数 C，则 C=\alpha C+1。解得 C=\frac{n-1}{2}。

将原递推式与 \alpha C+1 相减

r_{i,x}-C=(\alpha r_{i-1,x}+1)-(\alpha C+1)\\ r_{i,x}-C=\alpha\left(r_{i-1,x}-C \right)

我们构造了一个以 \alpha 为公比的等差数列。根据等差数列通项公式

r_{i,x}-C=\alpha^i \left(r_{0,x}-C\right)

移项得解。 :::::

我们写出整体期望 e_i=\sum\limits_{x<y}f_{i,x,y}，答案为 e_k。将 f 的转移代入

e_i=\dfrac{n-5}{n-1} e_{i-1} +p \sum\limits_{x<y} (r_{i-1,x}+c_{i-1,y}+1)

代入性质 2 和 r 的递推式得

e_i=\dfrac{n-5}{n-1} e_{i-1} +n+\dfrac{2C}{n(n-1)} \left(\dfrac{n-3}{n-1}\right)^{i-1}\\ C=\sum_{x=1}^n \left(r_{0,x}-\dfrac{n-1}{2}\right)(n-2x+1)

我们有 f_{0,x,y}=[a_x>a_y]，根据 r 的定义 r_{0,x}=\sum\limits_{x \ne y} [a_x>a_y]=a_x-1。

解关于 e 的线性递推：

e_i=\left(\dfrac{n-5}{n-1}\right)^i e_0 +C_n^2 \dfrac{1-\left(\frac{n-5}{n-1}\right)^i}{2}+\dfrac{C\left(\left(\frac{n-3}{n-1}\right)^{i}-\left(\frac{n-5}{n-1}\right)^i\right)}{n}

求出初始逆序对数 e_0 后快速幂即可解决本题，复杂度 O(n \log n+\log k)。

const int N = 5e5 + 5;
int n, k, a[N];
struct BIT {
    int tr[N];
    void add(int x, int c) {
        for (; x <= n; x += lowbit(x)) tr[x] += c;
    }
    int ask(int x) {
        int res = 0;
        for (; x >= 1; x -= lowbit(x)) res += tr[x];
        return res;
    }
} B;

void _main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    if (n == 1) return cout << 0, void();
    const mint i2 = ~mint(2), n5 = mint(n - 5) / (n - 1), n3 = mint(n - 3) / (n - 1), c2 = mint(n) * (n - 1) / 2;
    mint e0 = 0;
    for (int i = 1; i <= n; i++) B.add(a[i], 1), e0 += i - B.ask(a[i]);
    mint C = 0;
    for (int i = 1; i <= n; i++) C += (a[i] - 1 - (n - 1) * i2) * (n - 2 * i + 1);
    mint ek = n5.pow(k) * e0 + c2 * (1 - n5.pow(k)) / 2 + (C * (n3.pow(k) - n5.pow(k))) / n; 
    cout << ek * c2.pow(k);
}

Bonus：模拟赛 T4 在这个基础上套个 P12685 就是正解。二合一觉得自己很牛吗。