大棚网站建设/嘉兴新站seo外包

Tyvj 1172 自然数拆分Lunatic版

题意：给定一个自然数n（1<= n <= 4000）， 要求把自然数n拆分成n个正整数相加的情况（正整数可以重复出现， 但顺序不同仍视为同一种情况qaq）

求方案数mod 2147483648的值

完全背包求方案数（又双叒叕不开long long 见祖宗）

1 ~ n可以视为n种物品， 每种物品均可无限次使用， 背包容积为n， 求最终装满背包的方案数

完全背包板子上！ 

边界dp[0] = 1, 最终记得将ans - 1

不开long long 或者 unsigned int 只有一半的分数

#include<cstdio>
#include<iostream>
using namespace std;
const int sz = 4040, mod = 2147483648;
int n, ans = 0;
unsigned int dp[sz];
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;if(dp[n] > 0) ans = dp[n] - 1;else ans = mod;printf("%d", ans);return 0;
}