背景
对于一个排列P,逆序对指的是满足i 我们的任务便是寻找具有K个逆序对的排列数量，注意这里我指的是数量而非具体的排列，例如长度为3且具有2个逆序对的排列有2个，分别为231和312，但它们都只算一种排列。 最简单的方法就是使用暴力法，先生成所有排列，对于每个排列计算其逆序对并统计数量，最终输出符合条件的排列数量。代码如下：解题思路
1.暴力法
#include <bits/stdc++.h>
#define maxn 10
using namespace std;
int a[maxn];
int N,K,Ans;//N表示排列长度，K表示逆序对数量，Ans表示方案数
//计算逆序对数量
int calc(){
int res=0;
for(int i=1;i<N;i++)
for(int j=i+1;j<=N;j++)
if(a[i]>a[j])res++;
return res;
}
//搜索
void dfs(int dep){
if(dep==N+1){//搜索完毕，计算逆序对数量
int sum=calc();
if(sum==K)Ans++;
return;
}
for(int i=1;i<=N;i++){
if(!a[i]){
a[i]=dep;
dfs(dep+1);
a[i]=0;
}
}
}
int main(){
scanf("%d%d",&N,&K);
dfs(1);
printf("%d\n",Ans);
return 0;
}
该算法的时间复杂度为O(n*n!)，对于较大的n显然求解速度非常缓慢，因此我们需要考虑更快的方法。
2.动态规划
我们试图找到一个公式，用来快速计算具有K个逆序对的排列数量，考虑动态规划。假设dp[i][j]表示长度为i且含有j个逆序对的排列数量，那么这个状态应该是可以转移的，最后我们用dp[n][K]求解即可。现在我们来考虑dp[i][j]如何通过转移得到dp[i+1][j]。
考虑将数a插入一个长度为i的排列中，我们可以想到两种插入方法：将a插入到前面或者将a插入到后面。为了方便，我们要将a赋值成i+1，这样就可以将a插入到排列末尾，然后枚举a前面的一个数b，如果b < i+1，则将a插入b后面，这样就在原来的排列基础上产生了一些新的逆序对。
考虑dp[i][j]如何转移到dp[i+1][j]。对于dp[i+1][j]来说，它应该由dp[i][j'] + new_pair'组成，其中j’表示一个小于等于j的数，显然j'越大新生成的逆序对越少，因此我们枚举j'，然后加上新的逆序对的数量，就可以得到dp[i+1][j]的值。
接下来，我们来分析一下新生成的逆序对数量如何计算。对于一个新加入的数i+1，假设它插入到位置k上，则会在原有的排列中比它大的位置k~i上产生新的逆序对，这些逆序对的数量为i+1-k，我们将这个数累加到dp[i][j']后就可以得到dp[i+1][j]的值。
最终的代码会相对复杂，这里只展示dp转移部分，具体实现可以参见：https://www.acwing.com/solution/content/61747/
ll dp[maxn][maxn];
ll C[maxn][maxn];//组合数(n,k)
void init(){
fill(dp[0],dp[0]+maxn*maxn,0);
fill(C[0],C[0]+maxn*maxn,0);
for(int i=0;i<maxn;i++){//计算组合数
C[i][0]=1;
for(int j=1;j<=i;j++){
C[i][j]=C[i-1][j]+C[i-1][j-1];
}
}
dp[1][0]=1;
}
void solve(){
for(int i=2;i<=n;i++){//枚举排列长度
for(int j=0;j<=k;j++){//枚举逆序对数量
for(int k=0;k<i;k++){//枚举新加入的数插入到位置k上
int pair=i-1-k;
if(j-pair<0)continue;
dp[i][j]+=dp[i-1][j-pair]*C[i-1][pair];
}
}
}
}
总结
本节所讲的就是找到具有K个逆序对的排列数量，正文中介绍了两种解法：暴力法和动态规划。暴力法非常直接，先生成所有排列，然后暴力计算逆序对数量，最终统计符合条件的排列数量。这种方法的时间复杂度为O(n*n!)，对于较大的n显然不太适用。而动态规划比较复杂，需要分析逆序对的产生方式，然后使用动态规划转移逆序对数量。动态规划的时间复杂度是O(n*n*k)，可以处理较大的n。
参考资料：