「HAOI 2009」逆序对数列

题目大意：求有多少种逆序对数为 $k$ 的长度为 $n$ 的排列。$n,k \leq 1000$

$f[i][j]$ 表示 $1 \cdots i$ 的排列有 $k$ 个逆序对的方案数，前缀和优化。

#include <cstdio>

const int N = 1005, mod = 10000;
int f[N][N], g[N][N], n, m;

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) { //前i个数
        f[i][0] = g[i][0] = 1;
        for (int j = 1; j <= m; ++j) { //j个逆序对
            int tmp = j < i ? 0 : g[i-1][j-i];
            f[i][j] = (f[i][j] + g[i-1][j] - tmp) % mod;
            g[i][j] = g[i][j-1] + f[i][j];
        }
    }
    printf("%d\n", f[n][m]);
    return 0;
}

时间复杂度 $O(nk)$