[HAOI2009] 逆序对数列

题意

给定 n 和 k，问由 1..n 组成的所有排列中，逆序对数恰好等于 k 的排列有多少个。

答案对 10000 取模。

思路

先看一个适合小数据验证的暴力：

cpp

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#include <bits/stdc++.h>
using namespace std;

const int MOD = 10000;

int n, k;
int perm[15];
int used[15];
int ans;

int count_inv() {
    int ret = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (perm[i] > perm[j]) {
                ret++;
            }
        }
    }
    return ret;
}

void dfs(int pos) {
    if (pos > n) {
        if (count_inv() == k) {
            ans++;
            if (ans >= MOD) {
                ans -= MOD;
            }
        }
        return;
    }

    for (int x = 1; x <= n; x++) {
        if (used[x]) {
            continue;
        }
        used[x] = 1;
        perm[pos] = x;
        dfs(pos + 1);
        used[x] = 0;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // brute.cpp：枚举所有排列，直接统计逆序对数。
    cin >> n >> k;
    memset(used, 0, sizeof(used));
    ans = 0;
    dfs(1);
    cout << ans << '\n';
    return 0;
}

暴力会枚举所有排列，再直接数逆序对个数。

正解的关键在于考虑“把最大值插进去”。

设 dp[i][j] 表示由 1..i 组成的排列中，逆序对数恰好为 j 的方案数。

当我们把最大的数 i 插入一个长度为 i-1 的排列时：

插在最右边，新增 0 个逆序对
插得越靠左，新增的逆序对数越多
最多新增 i-1 个逆序对

所以有转移：

dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + ... + dp[i-1][j-(i-1)]

但直接这样做，每个状态还要枚举一段，复杂度偏大。

观察到这其实是上一层 dp 的一段连续区间和，于是先做前缀和：

prefix[x] = dp[i-1][0] + ... + dp[i-1][x]

那么：

如果 j < i，dp[i][j] = prefix[j]
否则 dp[i][j] = prefix[j] - prefix[j-i]

这样每个状态都能 $O(1)$ 转移，总复杂度降到 $O(n*k)$ 。

代码

cpp

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#include <bits/stdc++.h>
using namespace std;

const int MOD = 10000;
const int MAXN = 1005;

int n, k;
int dp[2][MAXN];
int prefix_sum[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;

    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        int now = i & 1;
        int pre = now ^ 1;

        memset(dp[now], 0, sizeof(dp[now]));
        prefix_sum[0] = dp[pre][0];
        for (int j = 1; j <= k; j++) {
            prefix_sum[j] = prefix_sum[j - 1] + dp[pre][j];
            if (prefix_sum[j] >= MOD) {
                prefix_sum[j] -= MOD;
            }
        }

        for (int j = 0; j <= k; j++) {
            // 把数字 i 插入前 i-1 个数字形成的排列中，
            // 新增的逆序对数可以是 0..i-1。
            int left = j - (i - 1);
            if (left <= 0) {
                dp[now][j] = prefix_sum[j];
            } else {
                dp[now][j] = prefix_sum[j] - prefix_sum[left - 1];
                if (dp[now][j] < 0) {
                    dp[now][j] += MOD;
                }
            }
        }
    }

    cout << dp[n & 1][k] << '\n';
    return 0;
}

复杂度

时间复杂度 $O(n*k)$ ，空间复杂度 $O(k)$ 。

总结

这题的本质是一个“插入最大值”的计数 DP。

前缀和优化不是另起炉灶，而是把原本的连续求和转移改写成区间和，属于非常典型的 DP 优化套路。

[HAOI2009] 逆序对数列

目录

题意

思路

代码

复杂度

总结