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 in C++
#include <iostream>
#include <vector>
using namespace std;
const int MOD = 1000000007;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k; cin >> n >> k;
vector<vector<int>> dp(n+1, vector<int>(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] << "\n";
return 0;
}