P82902

整数划分问题

难度 3 级 初二
讨论 统计 22通过 64提交 34.4%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

将正整数n表示成一系列正整数之和,n=n1+n2+...+nk,且满足n1\gen2\ge......\genk\ge1,k\ge1。称为正整数n的一个整数划分。正整数n的不同划分个数称为其划分数。例如6的划分为:

6,

5+1,

4+2, 4+1+1,

3+3, 3+2+1, 3+1+1+1,

2+2+2,2+2+1+1,2+1+1+1+1,

1+1+1+1+1+1

即6的划分数为11个。

输入

一个正整数n,且n\ge1。

输出

一个正整数,表示n的划分数。

样例

样例 1
输入
6
输出
11

提示

数据规模和约定 对于100%的数据,n\le 100.

来源

分治专题

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交