Mảng cặp nghịch đảo K (K Inverse Pairs Array) trong C++

Cho n và k. Đếm số hoán vị của 1..n có đúng k cặp nghịch đảo (ia[j]). Kết quả modulo 1e9+7.

Ví dụ

n=3,k=1 → 2 (hoán vị [1,3,2] và [2,1,3]).

DP tối ưu O(nk)

dp[i][j] = số hoán vị 1..i có j cặp nghịch. Chèn số i vào vị trí tạo thêm 0..i-1 cặp nghịch: dp[i][j] = Σ dp[i-1][j-t] (t=0..min(i-1,j)). Tối ưu bằng prefix sum: dp[i][j] = dp[i][j-1] + dp[i-1][j] - (j>=i ? dp[i-1][j-i] : 0).

Chương trình C++

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;

class Solution {
public:
    int kInversePairs(int n, int k) {
        vector<vector<int>> dp(n+1, vector<int>(k+1,0));
        dp[0][0]=1;
        for(int i=1;i<=n;i++) {
            dp[i][0]=1;
            for(int j=1;j<=k;j++) {
                dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % MOD;
                if(j>=i) dp[i][j] = (dp[i][j] - dp[i-1][j-i] + MOD) % MOD;
            }
        }
        return dp[n][k];
    }
};

int main() {
    Solution ob;
    cout << ob.kInversePairs(4,2); // 5
    return 0;
}