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)
1#include <iostream>
2#include <vector>
3using namespace std;
4#define MOD 1000000007
5
6int kInversePairs(int n, int k) {
7 vector<vector<int>> dp(n+1, vector<int>(k+1, 0));
8 for (int i = 0; i <= n; ++i) {
9 dp[i][0] = 1;
10 for (int j = 1; j <= k; ++j) {
11 if (i == 0) {
12 dp[i][j] = 0;
13 } else {
14 dp[i][j] = (dp[i-1][j] + MOD - (j>=i ? dp[i-1][j-i] : 0)) % MOD;
15 dp[i][j] = (dp[i][j] + dp[i][j-1]) % MOD;
16 }
17 }
18 }
19 return (dp[n][k] + MOD - (k>0 ? dp[n][k-1] : 0)) % MOD;
20}
21
22int main() {
23 int n = 3, k = 1;
24 cout << kInversePairs(n, k) << endl;
25 return 0;
26}Similar to the C solution, the C++ version uses vectors for dynamic memory management. It uses the same logic to initialize and update the DP table, using modulo operation to keep the results under control.