Problem 28: Permutations with Inversions
Problem Statement: Count the number of permutations of numbers 1 through n that have exactly k inversions. Print the answer modulo 10^9+7.
Input
The first line contains two integers n and k.
Output
Print the number of such permutations modulo 10^9+7.
Examples
Input:
3 1
Output:
2
Solution Explanation
Method 1: Use dynamic programming where dp[i][j] counts the number of permutations of i elements with j inversions; update using possible positions for the ith element. Method 2: Use a generating function approach, although implementing it efficiently is more challenging compared to the DP method.
Solution in C++
#include
#include
using namespace std;
const int MOD = 1000000007;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k; cin >> n >> k;
vector> dp(n+1, vector(k+1,0));
dp[0][0] = 1;
for(int i = 1; i <= n; i++){
for(int j = 0; j <= k; j++){
for(int p = 0; p < i && j - p >= 0; p++){
dp[i][j] = (dp[i][j] + dp[i-1][j-p]) % MOD;
}
}
}
cout << dp[n][k] << "
";
return 0;
}