【实战题解】逆序对排列数

给定两个数n，k，如果1~n的某个排列p[]，在满足下面2个条件的时称之为美丽：
- p[1] < p[2]
- p[]的逆序对数目<=k
输出美丽的排列数目（取模1e9+7）

n, k = 200
n >= 3

思路

首先显然是一个经典的dp[s][t]=z：表示用1~s的数字构成的排列，逆序对数目为t的个数是z。

这个经典的dp解法比较多，比如我们可以每次转移的时候，看作是新添加了数字s，这样我们仅需枚举s所处的位置即可，其实也就是枚举新增加的逆序对数目p：

$$ dp[s][t] = \sum_{p=0}^{\min(s-1,t)}dp[s-1][t-p] $$

显然p的范围应该是[0, s-1]，但是考虑到dp中t的设计，所以最大也只能取t

当然上面这个做法的复杂度显然就是O(n^2^k)或者O(nk^2^)的，这个复杂度还可以优化一下（虽然在这个题里是可行的）。

其实这个优化也很容易看出来，我们先假设dp[s][<0] = 0，这样的话公式就可以去掉min值，也就可以转为，这样就可以O(nk)计算了：

$$ dp[s][t] = \sum_{p=0}^{s-1}dp[s-1][t-p] = dp[s-1][t] + dp[s][t-1] - dp[s-1][t-s] $$

如果不能理解上述式子，可以画格子图加深理解，计算过程略

另外dp还有一种思路，即每次添加的数字位置固定是最后一位，枚举添加数字的值，这个看似比较奇怪，但是由于逆序对本身只考虑值的相对大小，而非绝对值，所以也是可以的，用类似的思路也是可以优化到O(nk)的

当然记得初始化dp[0][0]=1

随后我们枚举p[1]和p[2]的值，baseInv就是后面n-2个元素和p[1] p[2]的逆序对数目，这是一个确切值，先计算。
invMax就是后n-2个元素，自己逆序对的最大数目。

这题来说，这里也可以暴力求解，不过还是使用了一个前缀和进行优化。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
const int maxn = 2e2 + 5;
int n, k;
int dp[maxn][maxn];
int pre[maxn][maxn];

signed main() 
{
    cin >> n >> k;
    dp[0][0] = 1;
    for (int s = 1; s <= n - 2; ++s)
    {
        for (int t = 0; t <= k; ++t) 
        {
            dp[s][t] = 0;
            for (int l = 0; l <= min(s - 1, t); ++l)
                dp[s][t] = (dp[s][t] + dp[s - 1][t - l]) % mod;
        }
    }
    for (int s = 0; s <= n - 2; ++s) 
    {
        pre[s][0] = dp[s][0];
        for (int t = 1; t <= k; ++t)
            pre[s][t] = (pre[s][t - 1] + dp[s][t]) % mod;
    }
    int ans = 0;
    for (int p1 = 1; p1 <= n; ++p1) 
    {
        for (int p2 = p1 + 1; p2 <= n; ++p2) 
        {
            int baseInv = p1 + p2 - 3;        // 基础的逆序对数
            if (baseInv > k)
                continue;
            int invMax = k - baseInv;        // 剩下 n-2 个数的逆序对数的上限
            ans += pre[n - 2][invMax];
            ans %= mod;
        }
    }
    cout << ans << endl;
    return 0;
}