#P1521. 求逆序对

求逆序对

题目描述

我们说(i,j)(i,j)a1,a2,,aNa_1,a_2,\cdots,a_N 的一个逆序对,当且仅当 i<ji<jai>aja_i>a_j。例如 [2,4,1,3,5][2,4,1,3,5] 的逆序对有 33 个,分别为 (1,3),(2,3),(2,4)(1,3),(2, 3), (2, 4)。现在已知 NNKK,求 1,2,3,,N1,2,3,\cdots,N 的所有特定排列,使得这些排列的逆序对的数量恰好为 KK。输出这些特定排列的数量。

例如 N=5N=5K=3K=3 的时候,满足条件的排列有 1515 个,它们是:

  • [1,2,5,4,3][1, 2, 5, 4, 3]
  • [1,3,4,5,2][1, 3, 4, 5, 2]
  • [1,3,5,2,4][1, 3, 5, 2, 4]
  • [1,4,2,5,3][1, 4, 2, 5, 3]
  • [1,4,3,2,5][1, 4, 3, 2, 5]
  • [1,5,2,3,4][1, 5, 2, 3, 4]
  • [2,1,4,5,3][2, 1, 4, 5, 3]
  • [2,1,5,3,4][2, 1, 5, 3, 4]
  • [2,3,1,5,4][2, 3, 1, 5, 4]
  • [2,3,4,1,5][2, 3, 4, 1, 5]
  • [2,4,1,3,5][2, 4, 1, 3, 5]
  • [3,1,2,5,4][3, 1, 2, 5, 4]
  • [3,1,4,2,5][3, 1, 4, 2, 5]
  • [3,2,1,4,5][3, 2, 1, 4, 5]
  • [4,1,2,3,5][4, 1, 2, 3, 5]

输入格式

输入共第一行,两个整数 NNKK

输出格式

1N1\cdots N 的逆序对数量为 KK 的特定排列的数量输出。为了避免高精度计算,请将结果对 1000010000 取模后再输出。

5 3
15

提示

数据范围及约定

对于全部数据,保证 N100N \le 100KN×(N1)/2K \le N\times (N-1)/2