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];
    }
};

LeetCode-629 K Inverse Pairs Array