【实战题解】逆序对排列数 给定两个数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; }