题目描述
我们说(i,j) 是 a1,a2,⋯,aN 的一个逆序对,当且仅当 i<j 且 ai>aj。例如 [2,4,1,3,5] 的逆序对有 3 个,分别为 (1,3),(2,3),(2,4)。现在已知 N 和 K,求 1,2,3,⋯,N 的所有特定排列,使得这些排列的逆序对的数量恰好为 K。输出这些特定排列的数量。
例如 N=5,K=3 的时候,满足条件的排列有 15 个,它们是:
- [1,2,5,4,3];
- [1,3,4,5,2];
- [1,3,5,2,4];
- [1,4,2,5,3];
- [1,4,3,2,5];
- [1,5,2,3,4];
- [2,1,4,5,3];
- [2,1,5,3,4];
- [2,3,1,5,4];
- [2,3,4,1,5];
- [2,4,1,3,5];
- [3,1,2,5,4];
- [3,1,4,2,5];
- [3,2,1,4,5];
- [4,1,2,3,5]。
输入格式
输入共第一行,两个整数 N 和 K。
输出格式
将 1⋯N 的逆序对数量为 K 的特定排列的数量输出。为了避免高精度计算,请将结果对 10000 取模后再输出。
5 3
15
提示
数据范围及约定
对于全部数据,保证 N≤100,K≤N×(N−1)/2。