0629. K Inverse Pairs Array
===========================
题目信息
--------
:题号: 0629
:难度: Hard
:主题: 排列、逆序对、精确计数、取模
:原题: `LeetCode 0629 `_
:重点: 排列恰好包含 1 到 n 各一次、逆序对按下标 inums[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``。
自建示例
--------
存在多个满足条件的排列:
.. code-block:: text
输入: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] 各有两个逆序对,共五个排列。
要求的逆序对数量不可能达到:
.. code-block:: text
输入:n = 3,k = 4
输出:0
解释:三个数的排列最多只有 3 个逆序对,因此不存在恰好含 4 个逆序对的排列。