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)
1using System;
2class KInversePairs {
3 public int kInversePairs(int n, int k) {
4 int MOD = 1000000007;
5 int[,] dp = new int[n + 1, k + 1];
6 for (int i = 0; i <= n; i++) {
7 dp[i, 0] = 1;
8 for (int j = 1; j <= k; j++) {
9 if (i > 0) {
10 dp[i, j] = (dp[i-1, j] + MOD - (j >= i ? dp[i-1, j-i] : 0)) % MOD;
11 }
12 dp[i, j] = (dp[i, j] + dp[i, j-1]) % MOD;
13 }
14 }
15 return (dp[n, k] + MOD - (k > 0 ? dp[n, k-1] : 0)) % MOD;
16 }
17 static void Main() {
18 int n = 3, k = 1;
19 KInversePairs kip = new KInversePairs();
20 Console.WriteLine(kip.kInversePairs(n, k));
21 }
22}The C# solution creates a 2D array for DP and iterates through the array while using the same recursive logic as the previous solutions. The modulo operation is crucial for managing large integer values as required by the problem's constraints.