普及⏱ 1000ms💾 256MB#P5144🏷️ 动态规划递推

题目描述

宝石行有 $n$ 颗一模一样的宝石,要分装到 $k$ 个无标签的锦囊里,每个锦囊至少一颗, 任意两种装法只在宝石数量组合上看是否相同(与锦囊排列顺序无关,如 $1,1,5$、$1,5,1$、$5,1,1$ 视为同一种)。

求不同的装法总数。

输入格式

一行,两个整数 $n$ 和 $k$,用单个空格隔开。

输出格式

一行,一个整数:不同的装法数。

数据范围

$$6 < n \le 200,\quad 2 \le k \le 6$$

样例输入 #1
7 3
样例输出 #1
4
样例输入 #2
200 6
样例输出 #2
4132096