题目描述

给定一个自然数N，要求把N拆分成若干个正整数相加的形式，参与加法运算的数可以重复。与“自然数拆分问题”类似，同样需要满足方案的不重复。

若满足集合A=B，则称这两种拆分方式是重复的。

例如 5 = 3 + 2 和 5 = 2 + 3, 就是重复的拆分方式。

现在需要你求满足条件的拆分有多少种？

输入格式:

第一行自然整数T，表示之后测试数据组数， 以后T行，每行一个自然数N，（1<N<=4000）

输出格式:

T行，每行输出一个整数，表示拆分的方案数，结果对2147483648取模。

输入样例:

2
6
7

输出样例:

11
15

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define LEN 4001
#define MOD 2147483648
int main () {
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        long long dp[LEN]={0};
           dp[0]=1;//自然数包含自身的情况,如：7=7
        for(int i=1;i<=n;i++){
            for(int j=i;j<=n;j++){
                dp[j]=(dp[j]+dp[j-i])%MOD;//递推式
            }
        }
        cout << dp[n] << endl;
    }
    return 0;
}