#794. #6077. 「2017 山东一轮集训 Day7」逆序对

#6077. 「2017 山东一轮集训 Day7」逆序对

题目描述

给定 n,kn, k,请求出长度为 nn 的逆序对数恰好为 kk 的排列的个数。答案对 109+710 ^ 9 + 7 取模。 对于一个长度为 nn 的排列 pp,其逆序对数即满足 i<ji \lt j 且 pi>pjp_i \gt p_j 的二元组 (i,j)(i, j) 的数量。

输入格式

一行两个整数 n,kn, k。

输出格式

一行,表示答案。

7 12
531

数据范围与提示

对于 20%20\% 的数据,n,k≤20n, k \leq 20;
对于 40%40\% 的数据,n,k≤100n, k \leq 100;
对于 60%60\% 的数据,n,k≤5000n, k \leq 5000;
对于 100%100\% 的数据,≤n,k≤100000,1≤k≤(n2)\leq n, k \leq 100000, 1 \leq k \leq \binom{n}{2}。