题目地址:http://poj.org/problem?id=2229

题目大意

大致题意是,一个数N能有几种拆分方式,拆分的数字必须是2的幂。

思路

刚开始用母函数试了一下,果断超时2333。。。

还是动态规划找下规律吧。

首先考虑N为奇数,奇数的话必然都是1开头,例如7

  1. 1+1+1+1+1+1+1 = 7
  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

把所有的1去掉,即

  1. 1+1+1+1+1+1 = 6
  2. 1+1+1+1+2
  3. 1+1+2+2
  4. 1+1+4
  5. 2+2+2
  6. 2+4

则此时和为6,也就是说,若N为奇数,则拆分数和N-1(偶数)的拆分数一样。

若N为偶数,则必然有两种情况:1开头和2开头,例如上面的6。而1开头的拆分数和N-1(奇数)的拆分数加上2开头的拆分数。将所有2开头的拆分数除以2,则数量和N/2的拆分数一致。例如6以2开头的拆分数(就是6/2=3的拆分数):

  1. $2+2+2 => 1+1+1 = 3$
  2. $2+4 => 1+2$

综上所述,有$dp[N] = dp[N-1] + dp[N\%2==0?N/2:0]$

AC代码

/*************************************************************************
    > File Name: 2229.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-09-20 日 15:42:21 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

int N;
int a[1000005];

void solve() {
    a[1] = 1;
    a[2] = 2;
    for(int i=3; i<=N; ++i)
        a[i] = (a[i-1] + (i%2==0 ? a[i/2] : 0)) % 1000000000;
    cout << a[N] << endl;
}

int main()
{
#ifdef Oj
    // freopen(".in", "r", stdin);
#endif
    cin.sync_with_stdio(false);
    cin >> N;
    solve();
    return 0;
}