0629. K Inverse Pairs Array¶
题目信息¶
- 题号:
0629
- 难度:
Hard
- 主题:
排列、逆序对、精确计数、取模
- 原题:
- 重点:
排列恰好包含 1 到 n 各一次、逆序对按下标 i<j 且 nums[i]>nums[j] 定义、统计恰好 k 个逆序对的排列数量
题目重述¶
给定整数 n 和 k,考虑由整数 1 到 n 各出现一次组成的全部排列。若下标满足 i < j 且排列中第 i 个数大于第 j 个数,则 (i, j) 是一个逆序对。
返回恰好包含 k 个逆序对的排列数量,并对 10^9 + 7 取模。n 位于 [1, 1000],k 位于 [0, 1000]。若 k 大于长度为 n 的排列能够具有的最大逆序对数,则答案为 0。
自建示例¶
存在多个满足条件的排列:
输入:n = 4,k = 2
输出:5
解释:[1,3,4,2]、[1,4,2,3]、[2,1,4,3]、[2,3,1,4]、[3,1,2,4] 各有两个逆序对,共五个排列。
要求的逆序对数量不可能达到:
输入:n = 3,k = 4
输出:0
解释:三个数的排列最多只有 3 个逆序对,因此不存在恰好含 4 个逆序对的排列。