README.md

629. K Inverse Pairs Array

For an integer array nums, an inverse pair is a pair of integers [i, j] where 0 <= i < j < nums.length and nums[i] > nums[j].

Given two integers n and k, return the number of different arrays consisting of numbers from 1 to n such that there are exactly k inverse pairs. Since the answer can be huge, return it modulo 109 + 7.

Example 1:

Input: n = 3, k = 0
Output: 1
Explanation: Only the array [1,2,3] which consists of numbers from 1 to 3 has exactly 0 inverse pairs.

Example 2:

Input: n = 3, k = 1
Output: 2
Explanation: The array [1,3,2] and [2,1,3] have exactly 1 inverse pair.

Constraints:

• 1 <= n <= 1000
• 0 <= k <= 1000

Solutions (Rust)

1. Solution

impl Solution {
    pub fn k_inverse_pairs(n: i32, k: i32) -> i32 {
        let n = n as usize;
        let k = k as usize;
        let mut dp = vec![vec![0_i32; k + 1]; n + 1];

        dp[1][0] = 1;

        for i in 2..=n {
            for j in 0..=k {
                dp[i][j] = dp[i - 1][j];
                if j > 0 {
                    dp[i][j] = (dp[i][j] + dp[i][j - 1]) % 1_000_000_007;
                }
                if j >= i {
                    dp[i][j] = (dp[i][j] - dp[i - 1][j - i]).rem_euclid(1_000_000_007);
                }
            }
        }

        dp[n][k]
    }
}