题目名称	414. [HAOI 2009]逆序对数列
输入输出	`permut.in/out`
难度等级	★★☆
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	10
题目来源	.Xmz 于2010-03-22加入
开放分组	全部用户
提交状态
分类标签	HAOI 递推前缀和
	分享题解

通过：138，提交：320，通过率：43.13%
_Itachi	100	0.000 s	0.00 MiB	C++
Bennettz	100	0.000 s	0.00 MiB	C++
Anonymity	100	0.000 s	0.00 MiB	C++
jhs	100	0.000 s	0.80 MiB	C++
BaDBoY	100	0.002 s	0.83 MiB	C++
jhs	100	0.007 s	1.60 MiB	C++
new ioer	100	0.010 s	0.27 MiB	C++
Fmuckss	100	0.011 s	0.32 MiB	C++
水中音	100	0.013 s	0.32 MiB	C++
QILIN	100	0.015 s	0.30 MiB	C++

关于逆序对数列的近10条评论(全部评论)
百题斩！！！！ kZime 2017-03-30 07:23 6楼
为什么加上一个MOD就对了？？？？？？？？？？？一脸懵逼 /----------分割线-----------------------------------------------/ 好了懂了。。。 HeHe 2017-03-20 10:06 5楼
论取模运算的大常数，少取几次模nmm都过了。。 _Itachi 2016-10-06 21:14 4楼
啊啊啊啊啊啊啊啊啊啊啊啊 KZNS 2016-03-16 11:30 3楼
偷懒没优化…… cstdio 2013-03-09 13:55 2楼
feng 2013-03-05 11:14 1楼

414. [HAOI 2009]逆序对数列

★★☆ 输入文件：permut.in 输出文件：permut.out 简单对比
时间限制：1 s 内存限制：128 MiB

【题目描述】

对于一个数列${a_i}$，如果有 $i \lt j$ 且 $a_i \gt a_j$，那么我们称 $a_i$ 与 $a_j$ 为一对逆序对数。

若对于任意一个由 $1 \sim n$ 自然数组成的数列，可以很容易求出有多少个逆序对数。

请求出逆序对数为 $k$ 的这样自然数数列有多少个。

【输入格式】

第一行为两个整数 $n$,$k$。

【输出格式】

写入一个整数，表示符合条件的数列个数，由于这个数可能很大，你只需输出该数对 $10000$ 求余数后的结果。

【样例输入】

4 1

【样例输出】

【样例解释】

下列 $3$ 个数列逆序对数都为 $1$；分别是 $[1,2,4,3] , [1,3,2,4] , [2,1,3,4]$。

【数据规模与约定】

对于 $30\%$ 的数据，保证有 $n \le 12$；

对于 $100\%$ 的数据，保证有 $n \le 1000，k \le 1000 $。