TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P5902
  • 题目
  • P5902自然数拆分-
    限制 : 时间限制 : - MS   空间限制 : 10240 KB
    问题描述

    一个自然数可以写成若干个小于等于自己的自然之和,这叫该自然数的一个分解。
    不同的分解是表示这个自然数分解成的所有自然数不完全相同。 例如:3=2+1和3=1+1+1表示不同的分解。而3=2+1和3=1+2为相同的分解。
    现在的任务是,给出一个自然数,要求所有不同的分解方案数 mod 1,000,000,007的值。

    输入格式

    一个自然数n。

    输出格式

    n的分解方案数mod 1,000,000,007的值("mod"就是C++的"%")。

    样例输入 1

    5

    样例输出 1

    7

    样例输入 2

    10

    样例输出 2

    42

    样例输入 3

    88888

    样例输出 3

    653960384

    提示

    n<=105

    做这个题之前先做3131和1334


    来源  感谢nodgd