[BZOJ1677]&&[Usaco2005 Jan]Sumsets 求和

2014-07-04
竞赛题解 / 模拟
BZOJUSACO

描述 Description

Farmer John commanded his cows to search for different sets of numbers that sum to a given number. The cows use only numbers that are an integer power of 2. Here are the possible sets of numbers that sum to 7: 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 Help FJ count all possible representations for a given integer N (1 <= N <= 1,000,000).

给出一个 N(1≤N≤10^6)，使用一些 2 的若干次幂的数相加来求之．问有多少种方法

输入格式 InputFormat

一个整数 N.

输出格式 OutputFormat

方法数．这个数可能很大，请输出其在十进制下的最后 9 位．

样例输入 SampleInput

99999

样例输出 SampleOutput

444422154

来源 Source

Silver

BZOJ 1677

代码 Code

找规律题。可得 \[ f[i]=\lbrace \begin{aligned} &f[i-1]+f[\frac{i}{2}] &,\quad i \quad Mod \quad 2=0 \\\\ &f[i-1] &,\quad i \quad Mod \quad 2 \neq 0 \end{aligned} \rbrace \]

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm> 
#include <cmath>
#include <stack>
using namespace std;
const int mod=1000000000;
int f[1000005];
int i,j,t,n,m,l,r,k,z,y,x;
inline int read()
{
    int x=0;char ch=getchar();
    while (ch<'0' || ch>'9') ch=getchar();
    while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return x;
}
int main()
{
    n=read();
    f[1]=1;
    for (i=2;i<=n;i+=2)
    {
        f[i]=f[i+1]=(f[i-1]+f[i/2])%mod;
    }
    printf("%d\n",f[n]);
    return 0;
}