下面给你 LeetCode 3193「统计逆序对的数目」的 Rust 实现，思路与 Java / TS 版本一致，但使用了 Rust 风格的前缀和 + 滚动数组，在保证可读性的同时尽量节省内存。

✅ Rust 实现（推荐）

impl Solution {
    pub fn number_of_permutations(n: i32, requirements: Vec<Vec<i32>>) -> i32 {
        const MOD: i64 = 1_000_000_007;

        let n = n as usize;

        // 将约束存入 HashMap
        let mut req = std::collections::HashMap::new();
        for r in requirements {
            req.insert(r[0] as usize, r[1] as i64);
        }

        // 检查第一个位置
        if req.get(&0).map_or(false, |&v| v != 0) {
            return 0;
        }

        // 最大逆序对数
        let max_inv = n * (n - 1) / 2;

        // dp[j] 表示当前长度排列中，逆序对数为 j 的方案数
        let mut dp = vec![0i64; max_inv + 1];
        dp[0] = 1;

        for i in 1..=n {
            // 前缀和
            let mut prefix = vec![0i64; max_inv + 1];
            prefix[0] = dp[0];
            for j in 1..=max_inv {
                prefix[j] = (prefix[j - 1] + dp[j]) % MOD;
            }

            // 计算新的 dp
            let mut new_dp = vec![0i64; max_inv + 1];
            for j in 0..=max_inv {
                let left = j.saturating_sub(i - 1);
                let right = j;

                let mut sum = prefix[right];
                if left > 0 {
                    sum = (sum - prefix[left - 1] + MOD) % MOD;
                }
                new_dp[j] = sum;
            }

            // 处理约束
            if let Some(&cnt) = req.get(&(i - 1)) {
                for j in 0..=max_inv {
                    if j as i64 != cnt {
                        new_dp[j] = 0;
                    }
                }
            }

            dp = new_dp;
        }

        // 最终结果
        if let Some(&cnt) = req.get(&(n - 1)) {
            dp[cnt as usize] as i32
        } else {
            (dp.iter().sum::<i64>() % MOD) as i32
        }
    }
}

🧠 核心思路（Rust 版）

状态定义

dp[j] = 当前长度的排列中，逆序对数为 j 的方案数

转移方程

插入数字 i 时，最多新增 i-1 个逆序对：

dp_new[j] = Σ dp_old[j-k], 0 ≤ k ≤ i-1

👉 用 前缀和 优化区间求和。

⏱️ 复杂度分析

LeetCode 官方数据范围（n ≤ 500）完全可接受。

✅ 示例测试

fn main() {
    let res = Solution::number_of_permutations(
        3,
        vec![vec![2, 2]],
    );
    println!("{}", res); // 输出 1
}

🚀 Rust 常见坑提醒

✅ 使用 i64 防止溢出

✅ saturating_sub 替代 max(0, j-i)

✅ 每次 DP 后立即清零不满足约束的状态

✅ % MOD 必须加在每一步累加上

如果你愿意，我可以帮你：

• ✅ 进一步压缩空间（单数组 + 反向遍历）

• ✅ 写 #[test] 单元测试

• ✅ 对比 Rust / Java / TypeScript 性能

• ✅ 手推 DP 表帮助你理解转移过程

随时告诉我 👍