0629. K Inverse Pairs Array

题目信息

题号:

0629

难度:

Hard

主题:

排列、逆序对、精确计数、取模

原题:

LeetCode 0629

重点:

排列恰好包含 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 个逆序对的排列。