链接:
https://www.acwing.com/problem/content/281/
题意:
给定一个自然数N，要求把N拆分成若干个正整数相加的形式，参与加法运算的数可以重复。
求拆分的方案数 mod 2147483648的结果。
思路:
多重背包, 不过不用枚举到n.
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const unsigned int MOD = 2147483648;
LL Dp[10010];
int n, m;
int main()
{
scanf("%d", &n);
Dp[0] = 1;
for (int i = 1;i < n;i++)
{
for (int j = i;j <= n;j++)
Dp[j] = (Dp[j]+Dp[j-i])%MOD;
}
printf("%lld\n", Dp[n]);
return 0;
}