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).

Input:

A single line with a single integer, N.

Output:

The number of ways to represent N as the indicated sum. Due to the potential huge size of this number, print only last 9 digits (in base 10 representation).

Sample Input:

7

Sample Output:

6

题目链接

这道题目用母函数超时，所以采用递推法。

dp[i]记录i可以被组成的种类数。

当i为奇数时:i可以被分为一个1和一个偶数，所以dp[i]=d[i-1]

当i为偶数时有两种情况:

  1. 有两个1，dp[i-2]
  2. 全是偶数，显然等于dp[i/2]

所以dp[i]=dp[i-2]+dp[i/2]

AC代码:

#pragma comment(linker, "/STACK:102400000,102400000")
//#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <climits>
#include <stdlib.h>
#include <deque>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>
#include <string>
#include <vector>
#include <bitset>
#include <complex>
#include <functional>
#include <fstream>
#include <ctime>
#include <stdexcept>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5+5;
const int mod = 1e9+7;
const double eps = 1e-8;
const double pi = asin(1.0)*2;
const double e = 2.718281828459;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
inline void fre() {freopen("in.txt", "r", stdin);/*freopen("out.txt", "w", stdout);*/}

int main() {
// fre();
	int n;
	while (~scanf("%d", &n)) {
		ll dp[maxn];
		mem(dp, 0);
		dp[0] = 1; dp[1] = 1;
		for (int i = 2; i <= n; ++i) {
			if (i % 2) {
				dp[i] = dp[i - 1];
				dp[i] %= mod;
			}
			else {
				dp[i] = dp[i - 2] + dp[i / 2];
				dp[i] %= mod;
			}
		}
		printf("%lld\n", dp[n]);
	}
    return 0;
}