题解

题意分析

题目要求计算 $n$ 个元素的排列中，恰好有 $k$ 个逆序的排列数量。

• 逆序：在排列中，如果 $i < j$ 但 $a_i > a_j$，则称 $(a_i, a_j)$ 为一个逆序。
• 输入：多组数据，每组数据给出 $n$（排列长度）和 $k$（目标逆序数），直到输入 $n = k = 0$ 时结束。
• 输出：对于每组数据，输出满足条件的排列数量。

解题思路

1. 动态规划递推关系

   • 设 $dp[i][j]$ 表示 $i$ 个元素的排列中，恰好有 $j$ 个逆序的排列数量。
   • 递推公式：$$dp[i][j] = \sum_{k=1}^{i} dp[i-1][j-(i-k)]$$ 其中，$k$ 表示当前插入的数字在排列中的位置，$(i - k)$ 表示该插入操作新增的逆序数。
   • 边界条件：
     • $dp[1][0] = 1$（只有一个元素时，逆序数为 $0$）。
     • $dp[1][k] = 0$（$k > 0$ 时，不可能有逆序）。
   • 预处理：由于 $n$ 最大为 $18$，$k$ 最大为 $200$，可以预先计算所有可能的 $dp[i][j]$ 并存储。

2. 代码实现

   • 预处理 $dp$ 数组：
     • 外层循环遍历 $i$（排列长度），内层循环遍历 $j$（逆序数）。
     • 对于每个 $i$ 和 $j$，计算所有可能的插入方式带来的贡献。
   • 查询时直接输出 $dp[n][k]$。

参考代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
using namespace std;
typedef long long ll;
ll dp[20][210];
int main(){
    dp[1][0]=1;
    for(int i=2;i<=18;i++){
        for(int j=0;j<=200;j++){
            for(int k=1;k<=i;k++){
                if(j-(i-k)>=0) dp[i][j]+=dp[i-1][j-(i-k)];
            }
        }
    }
    int a,b;
    while(scanf("%d%d",&a,&b)!=EOF&&a!=0){
        printf("%lld\n",dp[a][b]);
    }
    return 0;
}