Luogu P2513 [HAOI2009]逆序对数列

题目描述

https://www.luogu.com.cn/problem/P2513

Solution

我们令 $f[i][j]$ 表示填了前 $i$ 个数，逆序对的个数为 $j$

当我们加入数 $i+1$ 时，能够产生的新逆序对的个数为 $0$ 到 $i$，注意到转移是一个区间，所以我们可以使用差分

时间复杂度为 $O(n^2)$

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define maxn 1010
using namespace std;

const int p = 10000;

int n, m;

int f[maxn][maxn]; 

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

    cin >> n >> m; f[0][0] = 1;
    for (int i = 0; i < n; ++i) { 
        for (int j = 0; j <= m; ++j) { 
            if (!f[i][j]) continue;
            int l = j, r = min(m, j + i);
            f[i + 1][l] = (f[i + 1][l] + f[i][j]) % p;
            f[i + 1][r + 1] = (f[i + 1][r + 1] - f[i][j]) % p;
        }
        for (int j = 1; j <= m; ++j)
            f[i + 1][j] = (f[i + 1][j] + f[i + 1][j - 1]) % p;
    } cout << (f[n][m] + p) % p << "\n"; 
    return 0;
}