#P1006. 小核桃与切割数字

小核桃与切割数字

题目描述

给出一个数字,可以对它进行任意次切割:

例如数字 123 可以被切割成 1 和 23,或者 12 和 3,或者 1 和 2 和 3。

进行若干次切割之后,得到一些新数字,将这些新数字求和,问总共有多少种不同的求和结果。注意,不切割也是可以的。

输入格式

输入包含一个正整数 nn,表示初始的数字。

输出格式

输出一行一个正整数表示答案。

样例1 #1

样例输入1

123

样例输出1

4

样例1 #1

样例输入2

111

样例输出2

3

数据范围及提示

【样例解释 #1】

不切割,此时和为 123;切割成 1 和 23,求和为 24;切割成 12 和 3,求和为 15;切割成 1 和 2 和 3,求和为 6;共 4 种求和结果。

【数据范围】

测试点 nn \leq
1 10
2 100
3-4 1000
5-6 100000
7-8 10910^9
9-10 101810^{18}

统计

相关

在以下作业中: