【Tyvj1087】sumsets

2014-05-25
竞赛题解 / 动态规划
TYVJ

描述 Description

正整数 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，计算不同方案的数量（保留最后 9 位数字）。

输入格式 InputFormat

一个整数，表示正整数 N。

输出格式 OutputFormat

一个整数，表示不同方案的数量。

样例输入 SampleInput

27

样例输出 SampleOutput

114

Tyvj 1087

代码 Code

水。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define mod 1000000000;
int f[1000001];
int i,j,t,n,m,l,r,k,z,y,x;
int main()
{
    scanf("%d",&n);
    f[1]=1;
    for (i=2;i<=n;i++) f[i]=((i%2==0)?(f[i-1]+f[i>>1]):f[i-1])%mod;
    printf("%d\n",f[n]);
    return 0;
}