K 上升段

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23:02
输入文件 k.in 输出文件 k.out

【题目描述】

对于自然数 1..n 的一个排列 A[1..N] 可以划分为若干个单调递增序列。每个单调递增序列由连续元素 A[st..ed] 组成，且满足以下条件：

    1<=st,ed<=n;

    A[i]<A[i+1] (st<=i<=ed-1);

    ed=n 或者 A[ed] > A[ed+1] ；

例如：排列 1 2 4 5 6 3 9 10 7 8 可划分为 3 个单调递增序列 1 2 4 5 6； 3 9 10 ； 7 8 ；

所以我们称这是一个 3 上升段序列 。

现在给定 n 和 k , 求出 n 的全排列中的， k 上升段序列 的个数。

【输入格式】

输入仅有 1 行，包含两个数 n, k （ 1 < n <= 20, 1 < k <= n ）。

【输出格式】

输出 n 的所有 k 上升段的个数。

【样例输入】 

3 2

【样例输出】 

4

【提示】

说明，符合条件的排列是１３２，３１２，２１３，２３１