text: Number of permutation with K inversions | Set 2 | C ++ program for the above approach ; Function to count permutations with K inversions ; Store number of permutations with K inversions ; If N = 1 only 1 permutation with no inversion ; For K = 0 only 1 permutation with no inversion ; Otherwise Update each dp state as per the reccurrance relation formed ; Print final count ; Driver Code ; Given N and K ; Function Call
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; int numberOfPermWithKInversion ( int N , int K ) { int dp [ 2 ] [ K + 1 ] ; int mod = 1000000007 ; for ( int i = 1 ; i <= N ; i ++ ) { for ( int j = 0 ; j <= K ; j ++ ) { if ( i == 1 ) dp [ i % 2 ] [ j ] = ( j == 0 ) ; else if ( j == 0 ) dp [ i % 2 ] [ j ] = 1 ; else dp [ i % 2 ] [ j ] = ( dp [ i % 2 ] [ j - 1 ] % mod + ( dp [ 1 - i % 2 ] [ j ] - ( ( max ( j - ( i - 1 ) , 0 ) == 0 ) ? 0 : dp [ 1 - i % 2 ] [ max ( j - ( i - 1 ) , 0 ) - 1 ] ) + mod ) % mod ) % mod ; ; } } cout << dp [ N % 2 ] [ K ] ; } int main ( ) { int N = 3 , K = 2 ; numberOfPermWithKInversion ( N , K ) ; return 0 ; }