整数拆分

Description

一个整数总可以拆分为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。

Input

每组输入包括一个整数:N(1<=N<=1000000)。

Output

对于每组数据,输出f(n)%1000000000。

Sample Input

7

Sample Output

6

在刚拿到这道题的时候我是一筹莫展的,但是自己代入几个数推几遍之后,就发现了规律,而发现规律的过程中也借鉴了网络,网上大部分的思路也是这样的:像这样拆分整数时,拆出的式子对于奇数(2k+1)来说第一项总是1,减去这个1就是偶数(2k)的拆分,所以f(2k+1)=f(2k);而对于偶数,又有第一项是1的和第一项不是1的,对于第一项是1的部分,我们发现它的第二项也是1,也就是说减去这个1对拆分个数也没影响,即f(2k)[第一项是1]=f(2k-1)=f(2k-2);而对于第一项不是1的部分,我们发现把每一项都除以2与这个偶数的一半那个数的拆分一一对应,即f(2k)[第一项不是1]=f(k)。

由此我们看到每一个数的拆分都可以由前面的拆分推出来,但有对应关系数与数之间跨度比较大,所以需要用一个数组把它们每一项在递推的过程中都记下来才能维持递推的过程。

具体代码如下:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;

int f[1000010];

int main()
{
    int n;
    f[0] = 1;
    f[1] = 1;//对于0和1,它们只有一种拆分,由此开始递推。
    while(cin >> n)
    {
        for(int i = 2; i <= n; i++)
        {
            if(i % 2) f[i] = f[i-1];
            else
            {
                f[i] = (f[i-1] + f[i/2]) % 1000000000;
            }
        }
        cout << f[n] << endl;
    }
    return 0;
}
全部评论

相关推荐

05-07 17:58
门头沟学院 Java
wuwuwuoow:1.简历字体有些怪怪的,用啥写的? 2.Redis 一主二从为什么能解决双写一致性? 3.乐观锁指的是 SQL 层面的库存判断?比如 stock > 0。个人认为这种不算乐观锁,更像是乐观锁的思想,写 SQL 避免不了悲观锁的 4.奖项证书如果不是 ACM,说实话没什么必要写 5.逻辑过期时间为什么能解决缓存击穿问题?逻辑过期指的是什么 其实也没什么多大要改的。海投吧
点赞 评论 收藏
分享
mjasjon:这种trash中厂 简历过筛概率比大厂还低(除阿里系)
投递哔哩哔哩等公司6个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务