引入
今天刷题时找到了这两题：
两题都是黄题，但数据范围不一样。
题意：
给定 \(n,k\)，求 \(n\) 的全排列中逆序对数量为 \(k\) 的排列个数。具体可见洛谷题面。
解法
先看数据范围：一题 \(n,k\le 10^3\)，另一题 \(n\le 100,k\le 4950\)。可以猜到复杂度分别是 \(O(nk),O(n^2k)\)。
先讲 \(O(n^2k)\) 做法。
\(O(n^2k)\) 求解
第一眼看过去很懵逼，但明显是一道计数题，暴力搜肯定不行，那么记忆化搜索呢？等等：记忆化搜索不就是 dp 吗？何尝不大胆猜测一波？
很自然地，想到设 \(dp_{i,j}\) 表示 \(i\) 的全排列中逆序对数量为 \(j\) 的排列个数。答案就是 \(dp_{n,k}\)，边界也很好确定：
那么怎么转移？观察到，如果将 \(i-1\) 的全排列插入一个 \(i\)，那么新增逆序对数量将和插入位置直接相关：如果放在第 \(pos\) 个数前面，将新增 \((i-1)-pos+1=i-pos\) 个逆序对。如：放在第 \(1\) 个数前面时，后面的所有数都小于 \(i\)，就会产生 \(i-1\) 个逆序对，其他情况同理。（请思考为什么。）
于是考虑通过 \(dp_{i-1,l}\) 转移。考虑到插入全排列时会新增逆序对，所以转移时要略作调整。
关于 \(l\) 的边界：
-
左边界：当插入至 \(i-1\) 的全排列的最左端时，后面增加 \(i-1\) 个逆序对。所以我们只要求 \(i-1\) 的全排列生成 \(j-i+1\) 个逆序对，那么加起来就刚好是 \((j-i+1)+(i-1)=j\) 个逆序对。当然，\(j-i+1<0\) 时无意义，应全部舍去，所以和 \(0\) 取 \(\max\)。
-
右边界：当插入到最后时，无新增逆序对，所以 \(i-1\) 的全排列需要贡献全部 \(j\) 个。
此算法时间复杂度 \(O(n^2k)\)，空间复杂度 \(O(nk)\)，可以通过第一题。但通过第二题就需要优化了。
\(O(nk)\) 求解
这题的 dp 优化也十分典，加一个前缀和优化即可。维护 \(sum_{i,j}=\sum_{l=0}^{j}dp_{i,l}\)，每次算出 \(dp_{i,j}\) 后 \(sum_{i,j}=sum_{i,j-1}+dp_{i,j}\) 即可。
转移方程变为：
请思考为什么 \(j\ge i\) 时是减去 \(sum_{i-1,j-i}\)（可参考转移方程 \(1\)）。
后记
代码就不放啦！怕抄袭。
EOF