3193. 统计逆序对的数目

题目描述：

给定一个长度为n的二维数组$re$，其中$re[i] = [id_i, cnt_i]$，求存在多少个全排列perm满足对所有的$re[i]$都有$perm[0..id_i]$恰好有 $cnt_i$个逆序对

答案对1000000007取模

• 2 <= n <= 300
• 1 <= requirements.length <= n
• requirements[i] = [endi, cnti]
• 0 <= endi <= n - 1
• 0 <= cnti <= 400
• 输入保证至少有一个 i 满足 endi == n - 1 。
• 输入保证所有的 endi 互不相同。

思路：

首先观察题目类型是求全排列的数量，还要取模，大概率是dp

再看数据范围 n=300,m=400，dp的状态方程完全可以放的下二维的

所以我们考虑用$dp[i][j]$表示满足所有$id<=i$的re下，前i个数字 逆序对数量是j 的全排列数量

求解普通逆序对时，我们可以扫一遍数组，对于每个 $ar[i]$，求出$j<i$中$ar[j]>ar[i]$的数量并求和

在本题，我们也考虑用这种方式来进行状态的转移

对于$i$，我们只在乎$ar[i]$在$ar[1]-ar[i]$中的大小关系，如果$ar[i]$在这$i$个数中排最大，也就是排第$i$位，则不会产生新的逆序对，即$i - i = 0$，如果排最小，也就是排第1位，则会产生$i-1$个逆序对，如果排第$k$大，则会产生$i-k$个新的逆序对

所以，我们可以枚举$ar[i]$在$ar[1]-ar[i]$排第几来进行状态转移

对于状态为$dp[i][j]$，存在两种情况，一种是i-1层是没有限制的，另一种是i-1层是有固定值限制的

• 如果$i-1$处没有题目给定的逆序对数量限制，则枚举k，从0枚举到$min(i, j)$，$min(i, j)$是因为对于下标从0开始，到$i-1$的数组，长度为i，此时在末尾添加一个元素，逆序对一次最多只能产生$i$

  $dp[i][j] = \sum_{k=0}^{min(i,j)}dp[i-1][j-k]$

• 如果$i-1$处存在题目给定的逆序对数量限制，那只能从那一个状态转移过来，假设r代表则re中对应位置的cnt， 则$dp[i][j] = dp[i - 1][r]$，$r<=j<=r+i$

class Solution {
    const int mod = 1000000007;
public:
    int numberOfPermutations(int n, vector<vector<int>>& re) {
        vector<int>p(n, -1);
        for(auto x : re){
            p[x[0]] = x[1];
        }
        int m = p[n - 1];
        vector<vector<int>> dp(n, vector<int>(m + 1));
        dp[0][0] = 1;
        for(int i = 1; i < n; ++i){
            if(p[i - 1] == -1){//无限制
                for(int j = 0; j <= m; ++j){
                    for(int k = 0; k <= min(i, j); ++k){
                        dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % mod;
                    }
                }
            }
            else{//有限制
                for(int j = p[i - 1]; j <= min(m, p[i - 1] + i); ++j){
                    dp[i][j] = dp[i - 1][p[i - 1]];
                }
            }
        }
        return dp[n - 1][p[n - 1]];
    }
};

也可以用记忆化搜索实现：

class Solution {
    const int mod = 1000000007;
public:
    int numberOfPermutations(int n, vector<vector<int>>& re) {
        vector<int>p(n, -1);
        p[0] = 0;
        for(auto x : re){
            p[x[0]] = x[1];
        }
        if(p[0])return 0;
        int m = p[n - 1];
        vector<vector<int>> dp(n, vector<int>(m + 1, -1));
        auto dfs = [&] (auto&& dfs, int i, int j){
            if(i == 0){
                return 1;
            } 
            if(dp[i][j] != -1)return dp[i][j];
            int & sum = dp[i][j];
            sum = 0;
            if(p[i - 1] == -1){
                for(int k = 0; k <= min(i, j); ++k){
                    sum = (sum + dfs(dfs, i - 1, j - k)) % mod;
                }
            }
            else {
                if(j >= p[i - 1] && j <= i + p[i - 1]){
                    sum = dfs(dfs, i - 1, p[i - 1]);
                }
            }
            return sum;
        };
        return dfs(dfs, n - 1, p[n - 1]);
    }
};

这样写的时间复杂度是O(n * m * min(n, m))，空间复杂度是O(n * m)

优化

我们可以发现对于无限制的那段$dp[i][j]$是一个连续的区间加法，可以用前缀和来优化枚举k的过程，要注意下标写对了

甚至还可以用滚动数组把空间降下来，这里懒得写了

class Solution {
    const int mod = 1000000007;
public:
    int numberOfPermutations(int n, vector<vector<int>>& re) {
        vector<int>p(n, -1);
        for(auto x : re){
            p[x[0]] = x[1];
        }
        int m = p[n - 1];
        vector<vector<int>> dp(n, vector<int>(m + 1, 0));
        dp[0][0] = 1;
        for(int i = 1; i < n; ++i){
            int mx = p[i] == -1 ? m : p[i];
            if(p[i - 1] == -1){//无限制
                vector<int>pre(m+1, 0);
                pre[0] = dp[i - 1][0];
                for(int j = 1; j <= m; ++j)pre[j] = (pre[j - 1] + dp[i - 1][j])%mod;
                for(int j = 0; j <= mx; ++j){
                    dp[i][j] = (pre[j] - (j - min(i, j) == 0 ? 0 : pre[j - min(i, j) - 1]) + mod) % mod;
                }
            }
            else{//有限制
                for(int j = p[i - 1]; j <= min(mx, p[i - 1] + i); ++j){
                    dp[i][j] = dp[i - 1][p[i - 1]];
                }
            }
        }
        return dp[n - 1][p[n - 1]];
    }
};