#P1176. 整数拆分

    ID: 188 传统题 1000ms 128MiB 尝试: 0 已通过: 0难度: 普及 ← 上一题 下一题 → 随机一题 上传者: 标签 搜索 记忆化搜索 动态规划 计数
显示设置

整数拆分

题目描述

把正整数 nn 拆成若干个正整数之和,交换加数顺序视为同一种拆分(例如 3+13+1 与 1+31+3 是同一种),并且要求每个加数都不超过 kk。

请你计算一共有多少种不同的拆分方案。

输入格式

一行两个整数 n,kn,k。

输出格式

一行一个整数,表示方案数。

输入输出样例 #1

输入 #1

5 3

输出 #1

5

说明

样例中 55 的拆分方案共有 55 种:3+23+2、3+1+13+1+1、2+2+12+2+1、2+1+1+12+1+1+1、1+1+1+1+11+1+1+1+1。

数据范围

  • 对于 100%100\% 的数据,1≤n≤3001\le n\le 300,1≤k≤3001\le k\le 300。答案在 6464 位有符号整数范围内。