题目描述 给定一个自然数N，要求把N拆分成若干个正整数相加的形式，参与加法运算的数可以重复。求拆分的方案数 mod 2147483648的结果。1≤N≤4000。 输入 一个整数n。 输出 输出一个数，即所有方案数 因为这个数可能非常大，所以你只要输出这个数 mod 2147483648 的余数即可。 样例输入 Copy 7 样例输出 Copy 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
完全背包 dp[0]=1.体积恰好是0 dp[1]=0;如果一个都没有的话，不可能选体积为1的。所以不合法
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=4005; const ll MOD=2147483648 ; ll dp[N]; int n; int main() { cin>>n; dp[0]=1; for(int i=1;i<=n-1;i++) { for(int j=i;j<=n;j++) dp[j]=(dp[j]+dp[j-i])%MOD; } cout<<dp[n]<<endl; }