อาร์เรย์คู่ผกผัน K คู่ (K Inverse Pairs Array) ใน C++

ภาพรวมปัญหา

กำหนด n และ k หาจำนวนอาร์เรย์ที่เป็นการเรียงสับเปลี่ยนของ 1..n ที่มี inverse pairs ทั้งหมด k คู่ Inverse pair: i < j และ a[i] > a[j] คำตอบ mod 1e9+7

ตัวอย่าง

n=3, k=1 → Output: 2 ([1,3,2] และ [2,1,3])

แนวทางแก้ปัญหา (Dynamic Programming)

dp[i][j] = จำนวนการเรียงสับเปลี่ยนของ 1..i ที่มี j inverse pairs
dp[0][0] = 1
Transition: ใส่ i ลงไปในตำแหน่งต่างๆ ของการเรียง i-1 จะเพิ่ม inverse pairs 0 ถึง i-1
dp[i][j] = dp[i][j-1] + dp[i-1][j] - (j>=i ? dp[i-1][j-i] : 0) (mod m)
ใช้ prefix sum optimization ทำให้ O(nk)

ตัวอย่างโปรแกรม

#include <bits/stdc++.h>
using namespace std;

const int m = 1e9 + 7;

class Solution {
public:
    int kInversePairs(int n, int k) {
        vector<vector<int>> dp(n + 1, vector<int>(k + 1));
        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];
                dp[i][j] %= m;
                if(j >= i) {
                    dp[i][j] = (dp[i][j] - dp[i - 1][j - i] + m) % m;
                }
            }
        }
        return dp[n][k];
    }
};

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

Input

4 2