Description
给定\(n\)和\(k\)，求包含数字\(1 \ldots n\)且恰好有\(k\)个逆序对的数组方案数。答案对\(10^9+7\)取模
Constraints
- \(1 \le n \le 1000\)
- \(0 \le k \le 1000\)
Solution
设\(dp[i][j]\)为使用\(1 \ldots i\)构成长度\(i\)的数组，且恰有\(j\)个逆序对的方案数。这里下标从1开始算起
问题在于怎么做状态转移
如果算出\(dp[i-1]\)的答案，把数字\(i\)插入到原\(1 \ldots i-1\)中，则得到\(dp[i]\)
而不同位置会产生不同的逆序对，其增加的数目显然在\([0, i-1]\)内
因此有：\(dp[i][j] = \sum_{k = 0}^{i-1}dp[i-1][j-k]\)
而这个式子直接算的话需要\(O(n^2k)\)，显然超时，因此加一个前缀和降低复杂度到\(O(nk)\)
Note: 如果集合为空，则方案数设为0（\(i==0\)）
Code
class Solution {
public:
int kInversePairs(int n, int k) {
auto dp = vector<vector<long>>(2, vector<long>(k+1));
auto pre = dp;
constexpr long MOD = 1e9 + 7;
for(int i = 1; i <= n; ++i) {
dp[i & 1][0] = pre[i & 1][0] = 1;
for(int j = 1; j <= k; ++j) {
auto sum = pre[i-1 & 1][j];
if(j-i >= 0) sum -= pre[i-1 & 1][j-i];
dp[i & 1][j] = (sum + MOD) % MOD;
pre[i & 1][j] = (pre[i & 1][j-1] + dp[i & 1][j]) % MOD;
}
}
return dp[n & 1][k];
}
};