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 <stdio.h>
2#define MOD 1000000007
3
4int kInversePairs(int n, int k) {
5 int dp[n+1][k+1];
6 for (int i = 0; i <= n; i++) {
7 for (int j = 0; j <= k; j++) {
8 if (j == 0) {
9 dp[i][j] = 1;
10 } else {
11 dp[i][j] = 0;
12 if (i > 0) {
13 dp[i][j] = (dp[i-1][j] + MOD - (j>=i ? dp[i-1][j-i] : 0)) % MOD;
14 }
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 printf("%d\n", kInversePairs(n, k));
25 return 0;
26}This solution initializes a DP table and iteratively fills it up using the recursive formula derived for permutation inverses. The modulo operation ensures that the values remain within bounds and computationally manageable.