[51Nod 1383] 整数分解为2的幂

Description

任何正整数都能分解成2的幂，给定整数N，求N的此类划分方法的数量！由于方案数量较大，输出Mod 1000000007的结果。
比如N = 7时，共有6种划分方法。
7=1+1+1+1+1+1+1
=1+1+1+1+1+2
=1+1+1+2+2
=1+2+2+2
=1+1+1+4
=1+2+4
输入一个数N（1 <= N <= 10^6)
输出划分方法的数量Mod 1000000007

Solution

这题其实真的很水，真的。

1很特殊，特殊的东西特殊搞。

这题观察一下题目，好像可以递推一下。

设方案数为f[i]

观察等式，发现1很特殊，特殊的东西特殊搞。
划分方法要么有1，要么没有1，也就是全是偶数。

有1，那就显然可以从f[i−1]转移而来，每个加上1就变成了i
没有1，那就全是偶数嘛，全是偶数那就可以全部除个2嘛，于是又可以从f[i/2]转移而来（当然奇数是没有的）

所以f[i]=f[i−1]+f[i/2]

然后？没有然后了。

Code

就这么短……

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define N 1000005
#define mo 1000000007
using namespace std;
int n,m,f[N];
int main()
{
    cin>>n;
    f[1]=1;
    fo(i,2,n)
    {
        if(i%2==0) f[i]=(f[i-1]+f[i/2])%mo;
        else f[i]=f[i-1];
    }
    cout<<f[n];
}