解题思路

本题等价于把正整数 $n$ 划分为恰好 $k$ 个正整数的有序序列。直接的划分型动态规划如下：

设 dp[s][t] 表示用恰好 t 枚硬币，面额之和为 s 的有序方案数。 转移时，最后一枚硬币取值为 x (1 ≤ x ≤ s)，那么前面 t-1 枚的和是 s-x，于是：

题面描述

给定两个正整数 $n,k$。你有面额为 $1,2,3,\ldots,10^9$ 的硬币，每种面额数量无限。你必须恰好选出 $k$ 枚硬币，并且要求它们的总面额之和为 $n$。 选择的顺序不同视为不同方案（如 $2,1$ 与 $1,2$ 记为两种）。求满足条件的方案数；

输入输出

输入： 一行两个整数 $n,k$。

输出： 输出一个整数，表示恰好用 $k$ 枚硬币凑成面额 $n$ 的方案数。

数据范围

• $1 \le n \le 63$
• $1 \le k \le n$

样例

输入

3 2

输出

2

说明 可行序列：1,2，2,1。

输入

4 3

输出

3

说明 可行序列：1,1,2，1,2,1，2,1,1。