CSES2229 排列逆序
#CS2229. 排列逆序
排列逆序
题目背景
翻译自 CSES-29 题。
题目描述
你的任务是计算出 1,2,…,n1, 2, \dots, n1,2,…,n 的所有排列中，恰好有 k 个逆序对（即元素的顺序不正确）的排列个数。
例如，当 n=4n = 4n=4 且 k=3k = 3k=3 时，有 6 个这样的排列：
[1, 4, 3, 2]
[2, 3, 4, 1]
[2, 4, 1, 3]
[3, 1, 4, 2]
[3, 2, 1, 4]
[4, 1, 2, 3]
输入格式
唯一的输入行包含两个整数 n 和 k。
输出格式
输出一个整数：表示恰好有 k 个逆序对的排列数目，结果需要对 109+710^9 + 7109+7 取模。
样例
4 3
6
样例1解释 逆序对是指一个排列中存在的两个元素 a[i]a[i]a[i] 和 a[j]a[j]a[j]，使得 i<ji < ji<j 且 a[i]>a[j]a[i] > a[j]a[i]>a[j]。
说明/提示