Sponsored
Sponsored
We use a two-dimensional dynamic programming array, where dp[i][j] represents the number of permutations of array {1, 2, ..., i} with exactly j inverse pairs. The transition is based on the idea that when we insert a new element into an existing permutation, it can create new inverse pairs from 0 up to i-1.
Time Complexity: O(n*k)
Space Complexity: O(n*k)
1def kInversePairs(n, k):
2 MOD = 1000000007
3 dp = [[0] * (k + 1) for _ in range(n + 1)]
4 for i in range(n + 1):
5 dp[i][0] = 1
6 for j in range(1, k + 1):
7 if i > 0:
8 dp[i][j] = (dp[i-1][j] + MOD - (dp[i-1][j-i] if j >= i else 0)) % MOD
9 dp[i][j] = (dp[i][j] + dp[i][j-1]) % MOD
10 return (dp[n][k] + MOD - (dp[n][k-1] if k > 0 else 0)) % MOD
11
12n = 3
13k = 1
14print(kInversePairs(n, k))The Python solution uses nested loops to fill the DP table with initial values followed by recursive updates based on previous results. Lists handle dynamic allocation and data storage, and modulo ensures numerical stability.