首页 > 代码库 > POJ 2229 Sumsets (递推&整数划分变形)
POJ 2229 Sumsets (递推&整数划分变形)
http://poj.org/problem?id=2229
思路:假设加数按从小到大的顺序。当n为奇数时,第一个数必须为1,此时f(n)=f(n-1);当n为偶数时,分两种情况讨论,若第一个数为1,则f(n)=f(n-1),若第一个数不为奇数,则所有数都不为奇数,提出一个公因子2出来,就是f(n/2),所以,f(n)=f(n-1)+f(n/2)
完整代码:
/*63ms,4300KB*/ #include<cstdio> const int mod = 1e9; const int maxn = 1000001; int f[maxn]; int main() { int n, i; f[1] = 1, f[2] = 2; for (i = 3; i < maxn; ++i) f[i] = (i & 1 ? f[i - 1] : (f[i - 2] + f[i >> 1]) % mod) ; while (~scanf("%d", &n)) printf("%d\n", f[n]); return 0; }
POJ 2229 Sumsets (递推&整数划分变形)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。