/ Vijos / 题库 /

整数划分[3]

整数划分[3]

时间限制:1秒  内存限制:256M


【问题描述】

  给定一个正整数 \(N\),需要把它划分成至少两个不同的整数和,问有多种不同的分解方案?例如 \(N = 7\) 时,有如下 \(4\) 种分解方案:
    \(7 = 1 + 6\)
    \(7 = 2 + 5\)
    \(7 = 3 + 4\)
    \(7 = 1 + 2 + 4\)

【输入格式】

  输入一个正整数 \(N\)。

【输出格式】

  输出一个整数,表示 \(N\) 的分解方案数,这个数可能很大,请 \(mod \ (10^9+7)\) 后输出。

【输入输出样例】

 Input

7

 Output

4

【数据限制】

  \(50\%\)的数据满足:\(3 ≤ N ≤ 140\)
  \(100\%\)的数据满足:\(3 ≤ N ≤ 10000\)

【来源】

  Mr.he

信息

ID
1011
难度
2
分类
动态规划 | 递推 | 搜索 点击显示
标签
递交数
1
已通过
1
通过率
100%
被复制
6
上传者