K Inverse Pairs Array

hard dp math

Problem

Count permutations of 1..n with exactly k inverse pairs (modulo 10^9+7).

Inputn=3 k=1

Output2

Permutations [1,3,2] and [2,1,3] each have 1 inversion.

input

def k_inverse_pairs(n, k):
    MOD = 10**9 + 7
    dp = [0] * (k + 1); dp[0] = 1
    for i in range(1, n + 1):
        nxt = [0] * (k + 1); pref = 0
        for j in range(k + 1):
            pref = (pref + dp[j]) % MOD
            if j >= i: pref = (pref - dp[j - i]) % MOD
            nxt[j] = pref
        dp = nxt
    return dp[k] % MOD

function kInversePairs(n, k) {
  const MOD = 1e9 + 7;
  let dp = new Array(k + 1).fill(0); dp[0] = 1;
  for (let i = 1; i <= n; i++) {
    const nxt = new Array(k + 1).fill(0); let pref = 0;
    for (let j = 0; j <= k; j++) {
      pref = (pref + dp[j]) % MOD;
      if (j >= i) pref = (pref - dp[j - i] + MOD) % MOD;
      nxt[j] = pref;
    }
    dp = nxt;
  }
  return Number(dp[k]);
}

int kInversePairs(int n, int k) {
    long MOD = 1_000_000_007L;
    long[] dp = new long[k + 1]; dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        long[] nxt = new long[k + 1]; long pref = 0;
        for (int j = 0; j <= k; j++) {
            pref = (pref + dp[j]) % MOD;
            if (j >= i) pref = (pref - dp[j - i] + MOD) % MOD;
            nxt[j] = pref;
        }
        dp = nxt;
    }
    return (int) dp[k];
}

int kInversePairs(int n, int k) {
    const int MOD = 1e9 + 7;
    vector dp(k + 1, 0); dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        vector nxt(k + 1, 0); long pref = 0;
        for (int j = 0; j <= k; j++) {
            pref = (pref + dp[j]) % MOD;
            if (j >= i) pref = (pref - dp[j - i] + MOD) % MOD;
            nxt[j] = pref;
        }
        dp = nxt;
    }
    return (int) dp[k];
}

Explanation

We want to count how many ways to arrange 1..n end up with exactly k "inverse pairs" (a bigger number sitting before a smaller one). Instead of building permutations, we count them with a dynamic program that adds one number at a time.

The key idea: when we insert the number i into an arrangement of the first i-1 numbers, we can place it in different slots, and each slot adds between 0 and i-1 new inversions. So the count for i numbers with j inversions is the sum of a window of the previous row.

Summing a window again and again is slow, so we use a running prefix sum pref. As j grows we add dp[j], and once the window gets too wide (when j >= i) we subtract dp[j - i] to slide it. Everything is kept modulo 10^9 + 7.

Example: for n = 3, k = 1, after processing all three numbers the answer is 2, matching the permutations [1,3,2] and [2,1,3] that each have one inversion.

Because each row is built with one pass using the sliding prefix sum, the whole thing runs in O(n*k) time instead of anything exponential.

Time: O(n·k) Space: O(k)