K Inverse Pairs Array: อาร์เรย์ที่มี Inverse Pairs จำนวน K ใน C++

ปัญหา

กำหนด n และ k หาจำนวน Permutation ของ 1..n ที่มี Inverse Pairs ทั้งหมด กี่คู่ Inverse Pair = คู่ (i, j) ที่ i < j และ a[i] > a[j] คำตอบ modulo 10^9 + 7

ตัวอย่าง: n=3, k=1 → Permutations: [1,3,2] (1 pair: 3>2), [2,1,3] (1 pair: 2>1) → 2 วิธี

แนวคิด: Dynamic Programming

State

dp[i][j] = จำนวน Permutation ของ 1..i ที่มี Inverse Pairs = j

Recurrence

พิจารณาใส่ตัวเลข i (ตัวใหญ่สุด) ลงใน Permutation ของ 1..i-1:

• ใส่ท้ายสุด → เพิ่ม 0 inverse pairs
• ใส่หน้าสุด → เพิ่ม i-1 inverse pairs
• โดยทั่วไป ใส่ที่ตำแหน่ง p (นับจากซ้าย 0-indexed) → เพิ่ม i-1-p inverse pairs

ดังนั้น:

dp[i][j] = Σ dp[i-1][j - x]  สำหรับ x = 0..min(j, i-1)

เพิ่มประสิทธิภาพด้วย Prefix Sum

dp[i][j] = dp[i][j-1] + dp[i-1][j]
if j >= i: dp[i][j] -= dp[i-1][j-i]

เพราะ dp[i][j-1] = Σ dp[i-1][j-1-x] และ dp[i-1][j] เพิ่ม term ใหม่เข้าไป

โค้ด 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][j] = (dp[i][j] + 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;
}

ตาราง DP ตัวอย่าง (n=4, k=2)

ความซับซ้อน

• Time: O(n × k)
• Space: O(n × k) (ลดเป็น O(k) ได้ด้วย Rolling Array)

Input / Output

Input:  n=4, k=2
Output: 5

Permutations ของ n=4, k=2

[1,4,3,2]  (4>3, 4>2, 3>2) → 3 pairs ❌
[2,1,4,3]  (2>1, 4>3) → 2 pairs ✓
[2,3,1,4]  (2>1, 3>1) → 2 pairs ✓
[3,1,2,4]  (3>1, 3>2) → 2 pairs ✓
[3,2,1,4]  (3>2, 3>1, 2>1) → 3 pairs ❌
[1,3,2,4]  (3>2) → 1 pair ❌
... รวม 5 permutations ที่มี 2 inverse pairs