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

    ID: 7246 传统题 1000ms 512MiB 尝试: 2 已通过: 1 难度: 8 上传者: 标签>CF2500省选/NOI-普通生成函数生成函数求系数计数 DP滚动数组阶乘逆元预处理

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

题目描述

给定 n,k n, k ,请求出长度为 n n 的逆序对数恰好为 k k 的排列的个数。答案对 109+7 10 ^ 9 + 7 取模。

对于一个长度为 n n 的排列 p p ,其逆序对数即满足 i<j i < j 且 pi>pj p_i > p_j 的二元组 (i,j) (i, j) 的数量。

输入格式

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

输出格式

一行,表示答案。

7 12
531

数据范围与提示

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