#188. 自然数拆分Lunatic版

自然数拆分Lunatic版

题目描述

输入自然数n,然后将其拆分成由若干数相加的形式,参与加法运算的数可以重复。

输入格式

输入只有一个整数n,表示待拆分的自然数n。 0<n<=4000 PS:0也算自然数,所以这里应该写正整数比较好 但是为了尊重原作者的版权(这有版权吗- -),没有改掉。 本来n是要到5000的,但是开到5000的话我的程序就Memory Limit Exceeded了。。

输出格式

输出一个数,即所有方案数 因为这个数可能非常大,所以你只要输出这个数 mod 2147483648 的余数即可。

样例输入

7

样例输出

14

提示

解释: 输入7,则7拆分的结果是 7=1+6 7=1+1+5 7=1+1+1+4 7=1+1+1+1+3 7=1+1+1+1+1+2 7=1+1+1+1+1+1+1 7=1+1+1+2+2 7=1+1+2+3 7=1+2+4 7=1+2+2+2 7=1+3+3 7=2+5 7=2+2+3 7=3+4

一共有14种情况,所以输出14 mod 2147483648,即14