2的幂

code

6 年前

2的幂

时间： 1ms 内存：128M

描述：

输入一个正整数n,输出用2的幂组合出n的方案数。
对于正整数7，它有6种表示方式：
1) 1+1+1+1+1+1+1
2) 1+1+1+1+1+2
3) 1+1+1+2+2
4) 1+1+1+4
5) 1+2+2+2
6) 1+2+4

输入：

一个正整数n，1<=n<=1000000

输出：

一个正整数，代表用2的幂组合出n的方案数，由于结果可能很大，仅保留后九位数字。

示例输入：

示例输出：

提示：

参考答案（内存最优[4908]）：

#include<stdio.h>
#include<stdlib.h>

int main()
{
    int a,i;
    int m [1000005];
    while (scanf("%d",&a)==1)
    {
        m[1] = 1;
        for (i = 2; i <= a; i++)
        {
            if (i % 2 == 0)
            {
                m[i] = (m[i - 1]+m[ i / 2])%1000000000;
            }
            else
            {
                m[i] = m[i - 1]%1000000000;
            }
        }
        printf("%d\n", m[a]%1000000000);
    }
    return 0;
}

参考答案（时间最优[3]）：

#include <iostream>

using namespace std;
int s[1000001];
typedef long long ll;
int main()
{
    ll N;
    cin>>N;

    s[1]=1;
    s[2]=2;
    for(int i=3; i<=N; i++)
    {

        if(i%2!=0)
            s[i]=s[i-1];
        else
        {
            s[i]=s[i-2]+s[i/2];
            s[i]=s[i]%1000000000;
        }
    }
    cout<<s[N]<<endl;
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。