[HAOI2009] 逆序对数列

发表于 | 分类于 >
字数统计 : 395   |   阅读时长 ≈ 2 mins.

题目

链接

[HAOI2009]逆序对数列

题意简述

求 $n \ (n <= 1000)$ 的全排列中逆序对个数为 $k \ (k <= 1000)$ 的数目。

思路

暴力

暴力枚举全排列 ，暴力统计。
时间复杂度： $O(!n * n^{2})$ 。
预期得分： $(30)$。

暴力-UDP

暴力枚举全排列 ，树状数组求逆序对。
时间复杂度： $O(!n * nlogn)$ 。
预期得分： $(30)$。

DP

新来的数是坠大的，所以把它插入到第 $pos$ 个位置会产生 $(n - pos - 1)$ 个逆序对。
状态转移方程：

时间复杂度： $O(n^{3})$ 。
预期得分： $(60)$。

DP-UDP

可以发现每次转移都是一段区间，考虑用前缀和维护。
时间复杂度： $O(n^{2})$ 。
预期得分： $(100)$。

代码

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
#include <bits/stdc++.h>
#define REG register
#define IN inline
#define For(x,y,z) for (REG int (x) = (y); (x) <= (z); ++(x))
#define FOR(x,y,z) for (REG int (x) = (y); (x) <  (z); ++(x))
const int kmax_num = 1e3 + 10, kmax_int = 2147483647, kmod = 1e4;

int n, m;
int f[kmax_num][kmax_num];

inline void Mod(REG int& num)	{
    while(num < 0)		num += kmod;
    while(num >= kmod)	num -= kmod;
    return ;
}

int main() {
    std::cin >> n >> m;

    f[2][0] = f[2][1] = 1;
    s[2][0] = 1, s[2][1] = 2, s[2][2] = 2, s[2][3] = 2;

    REG int sum;
    For(i,3,n)	{
        sum = 0;
        For(h,0,m)	{
            sum += f[i - 1][h];
            if(h - i >= 0)	sum -= f[i - 1][h - i];
            Mod(sum);
            f[i][h] = sum;
        }
    }
    printf("%d\n", f[n][m]);
    return 0;
}

杂项

  • 一开始没用前缀和 $TLE$ 还 $debug$ 了好久。
  • 原来的前缀和计算是用数组乱搞的，后来重构了。