/ Vijos / 题库 /

笨笨的车厢连接

笨笨的车厢连接

背景

笨笨:哇…………………………
路人甲:这回又是干嘛了啊……
笨笨:呀…………………………
路人甲:偶不认识他……
笨笨:啊…………………………
路人甲:- -、
(旁白:过山车……)

描述

大家都知道,过山车可以有很多的车厢……
为了车子的安全(笨笨继续:啊……),要把重的车厢排在轻的车厢前面,并且用连接链连上,若是轻的车厢在重的车厢前面,则不需要连接链。

每辆过山车有n节车厢,车厢的重量有1~n,并且各不相同。

笨笨现在想知道,有n节车厢的车子有多少种方法使连接链数为k。

格式

输入格式

输入有多行,每行两个数n,k(0<=k<=n<=200)。

输出格式

对于每个询问输出一个方法数,由于结果可能很大,所以输出结果mod 2009后的数即可。

样例1

样例输入1

5 2

样例输出1

66

限制

1s

提示

不明白的看过来~~
假设有3节车厢,则它们的重量为1、2、3
当k=1时,3 1 2是一个符合的方法,2 1 3也是,1 3 2、2 3 1这4种都是符合的方法。

来源

笨笨原创。

信息

ID
1584
难度
6
分类
组合数学 点击显示
标签
递交数
1218
已通过
371
通过率
30%
被复制
2
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

笨笨工作室2009普及组模拟赛