2025-01-23：统计逆序对的数目。用go语言，给定一个整数 n 和一个二维数组 requirements，其中每个元素 requirements[i] = [endi, cnti] 表示在要求中末尾的下标以及逆序对的数量。

在一个整数数组 nums 中，如果存在一个下标对 (i, j)，使得 i < j 且 nums[i] > nums[j]，则称这对 (i, j) 为逆序对。

任务是返回所有可能的数组排列 perm = [0, 1, 2, …, n - 1] 的数量，使得对于所有的 requirements，都满足 perm[0…endi] 中恰好有 cnti 个逆序对。

由于结果可能会非常大，请将结果对 1000000007 取余后返回。

2 <= n <= 300。

1 <= requirements.length <= n。

requirements[i] = [endi, cnti]。

0 <= endi <= n - 1。

0 <= cnti <= 400。

输入保证至少有一个 i 满足 endi == n - 1 。

输入保证所有的 endi 互不相同。

输入：n = 3, requirements = [[2,2],[0,0]]。

输出：2。

解释：

两个排列为：

[2, 0, 1]

前缀 [2, 0, 1] 的逆序对为 (0, 1) 和 (0, 2) 。

前缀 [2] 的逆序对数目为 0 个。

[1, 2, 0]

前缀 [1, 2, 0] 的逆序对为 (0, 2) 和 (1, 2) 。

前缀 [1] 的逆序对数目为 0 个。

答案2025-01-23：

chatgpt

题目来自leetcode3193。

大体步骤如下：

1.定义常量 MOD，表示取余值为 1e9 + 7。

2.编写函数 numberOfPermutations(n, requirements) 来计算符合要求的排列数量。

3.初始化一个要求映射 reqMap，记录每个末尾下标及其逆序对数量的要求。同时找出最大的逆序对数量 maxCnt。

4.构建动态规划数组 dp，用于存储计算结果，其中 dp[i][j] 表示前 i 个数中逆序对数量为 j 的排列数。

5.定义递归函数 dfs(end, cnt) 来计算符合要求的排列数量。

6.在 dfs 函数中，首先处理边界情况，然后根据当前位置是否存在逆序对要求进行不同的处理。

7.在主函数 main 中，给定 n = 3 和 requirements = [[2,2],[0,0]]，调用 numberOfPermutations 函数计算结果并打印输出。

总的时间复杂度：

• 针对每个位置及逆序对情况进行递归计算，时间复杂度为 O(n * maxCnt)。

• 最终结果取模操作的时间复杂度为 O(1)。

总的额外空间复杂度：

• 使用了 reqMap 来存储逆序对的要求，空间复杂度为 O(n)。

• 动态规划数组 dp 使用了二维数组来存储计算结果，空间复杂度为 O(n * maxCnt)。

因此，总的时间复杂度为 O(n * maxCnt)，总的额外空间复杂度为 O(n * maxCnt)。

Go完整代码如下：

package main

import (
	"fmt"
)

const MOD int64 = 1e9 + 7

func numberOfPermutations(n int, requirements [][]int) int {
    reqMap := make(map[int]int)
	reqMap[0] = 0
	maxCnt := 0
	for _, req := range requirements {
		reqMap[req[0]] = req[1]
		if req[1] > maxCnt {
			maxCnt = req[1]
		}
	}
	if reqMap[0] != 0 {
		return 0
	}

	dp := make([][]int64, n)
	for i := range dp {
		dp[i] = make([]int64, maxCnt + 1)
		for j := range dp[i] {
			dp[i][j] = -1
		}
	}

	var dfs func(int, int) int64
	dfs = func(end, cnt int) int64 {
		if cnt < 0 {
			return 0
		}
		if end == 0 {
			return 1
		}
		if dp[end][cnt] != -1 {
			return dp[end][cnt]
		}
		if r, exists := reqMap[end - 1]; exists {
			if r <= cnt && cnt <= end + r {
				dp[end][cnt] = dfs(end - 1, r)
				return dp[end][cnt]
			}
			return 0
		} else {
			if cnt > end {
				dp[end][cnt] = (dfs(end, cnt - 1) - dfs(end - 1, cnt - 1 - end) + dfs(end - 1, cnt) + MOD) % MOD
			} else {
				dp[end][cnt] = (dfs(end, cnt - 1) + dfs(end - 1, cnt)) % MOD
			}
			return dp[end][cnt]
		}
	}

	return int(dfs(n - 1, reqMap[n - 1]))
}

func main() {
	n := 3
	requirements := [][]int{{2,2},{0,0}}
	result := numberOfPermutations(n,requirements)
	fmt.Println(result)
}

Rust完整代码如下：

use std::collections::HashMap;

const MOD: i64 = 1_000_000_007;

fn number_of_permutations(n: usize, requirements: Vec<Vec<i32>>) -> i64 {
    let mut req_map: HashMap<i32, i32> = HashMap::new();
    req_map.insert(0, 0);
    let mut max_cnt = 0;

    for req in requirements {
        req_map.insert(req[0], req[1]);
        if req[1] > max_cnt {
            max_cnt = req[1];
        }
    }

    if *req_map.get(&0).unwrap() != 0 {
        return 0;
    }

    let mut dp = vec![vec![-1; (max_cnt + 1) as usize]; n];

    fn dfs(end: usize, cnt: i32, req_map: &HashMap<i32, i32>, dp: &mut Vec<Vec<i64>>) -> i64 {
        if cnt < 0 {
            return 0;
        }
        if end == 0 {
            return 1;
        }
        if dp[end][cnt as usize] != -1 {
            return dp[end][cnt as usize];
        }
        if let Some(&r) = req_map.get(&(end as i32 - 1)) {
            if r <= cnt && cnt <= end as i32 + r {
                dp[end][cnt as usize] = dfs(end - 1, r, req_map, dp);
            } else {
                return 0;
            }
        } else {
            if cnt > end as i32 {
                dp[end][cnt as usize] = (dfs(end, cnt - 1, req_map, dp) - 
                                          dfs(end - 1, cnt - 1 - end as i32, req_map, dp) + 
                                          dfs(end - 1, cnt, req_map, dp) + MOD) % MOD;
            } else {
                dp[end][cnt as usize] = (dfs(end, cnt - 1, req_map, dp) + 
                                          dfs(end - 1, cnt, req_map, dp)) % MOD;
            }
        }
        dp[end][cnt as usize]
    }

    return dfs(n - 1, *req_map.get(&(n as i32 - 1)).unwrap(), &req_map, &mut dp);
}

fn main() {
    let n = 3;
    let requirements = vec![vec![2, 2], vec![0, 0]];
    let result = number_of_permutations(n, requirements);
    println!("{}", result);
}

Python完整代码如下：

# -*-coding:utf-8-*-

MOD = 10**9 + 7

def number_of_permutations(n, requirements):
    req_map = {0: 0}
    max_cnt = 0

    for req in requirements:
        req_map[req[0]] = req[1]
        if req[1] > max_cnt:
            max_cnt = req[1]

    if req_map[0] != 0:
        return 0

    # 初始化动态规划表
    dp = [[-1] * (max_cnt + 1) for _ in range(n)]

    def dfs(end, cnt):
        if cnt < 0:
            return 0
        if end == 0:
            return 1
        if dp[end][cnt] != -1:
            return dp[end][cnt]

        if end - 1 in req_map:
            r = req_map[end - 1]
            if r <= cnt <= end + r:
                dp[end][cnt] = dfs(end - 1, r)
                return dp[end][cnt]
            return 0
        else:
            if cnt > end:
                dp[end][cnt] = (dfs(end, cnt - 1) - dfs(end - 1, cnt - 1 - end) + dfs(end - 1, cnt)) % MOD
            else:
                dp[end][cnt] = (dfs(end, cnt - 1) + dfs(end - 1, cnt)) % MOD
            return dp[end][cnt]

    return int(dfs(n - 1, req_map[n - 1]))

def main():
    n = 3
    requirements = [[2, 2], [0, 0]]
    result = number_of_permutations(n, requirements)
    print(result)

if __name__ == "__main__":
    main()