首页 > 代码库 > 每日一九度之 题目1084：整数拆分
每日一九度之 题目1084：整数拆分
时间限制：1 秒
内存限制：32 兆
特殊判题：否
提交：2720
解决：1099
- 题目描述：
一个整数总可以拆分为2的幂的和，例如：
7=1+2+4
7=1+2+2+2
7=1+1+1+4
7=1+1+1+2+2
7=1+1+1+1+1+2
7=1+1+1+1+1+1+1
总共有六种不同的拆分方式。
再比如：4可以拆分成：4 = 4，4 = 1 + 1 + 1 + 1，4 = 2 + 2，4=1+1+2。
用f(n)表示n的不同拆分的种数，例如f(7)=6.
要求编写程序，读入n(不超过1000000)，输出f(n)%1000000000。
- 输入：
每组输入包括一个整数：N(1<=N<=1000000)。
- 输出：
对于每组数据，输出f(n)%1000000000。
- 样例输入：
7
- 样例输出：
6
当n为奇数的时候，可以将其看成是其上一个偶数加上一个2的0次方，故 f（n） = f（n-1）。
当n为偶数的时候，又可以以一划分，对于含有1的情况：与n-1对应。对于没有1的情况：可以看成是n/2乘以2。所以：f（n） = f（n-1）+f（n/2）。
//Asimple#include <iostream>#include <algorithm>#include <cstring>#include <cstdio>#include <vector>#include <cctype>#include <cstdlib>#include <stack>#include <cmath>#include <set>#include <map>#include <string>#include <queue>#include <limits.h>#define INF 0x7fffffff#define mod 1000000000 using namespace std;const int maxn = 1000000+5;typedef long long ll;int n;int a[maxn];void init(){ a[0] = 0; a[1] = 1; a[2] = 2; for(int i=3; i<maxn; i++){ if( i % 2 ){ a[i] = a[i-1]; } else { a[i] = (a[i-1] + a[i/2])%mod; } } return ;} int main(){ init(); while( ~scanf("%d",&n) ){ printf("%d\n",a[n]); } return 0;}
每日一九度之 题目1084：整数拆分
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。