ACM模版

描述

题解

看到这里，我们应该可以想到，这是一个数论问题，应该是一个什么数列，暴力解出来小数据后，在 OEIS 中查看了一下下，发现的确是一个十分有趣的数列——Binary partition function: number of partitions of n into powers of 2.

很明显，这里

f[0]=f[1]=1
    f(2m+1)=f(2m)
               f(2m)=f(2m−1)+f(m)

所以呢，直接暴力预处理一下，然后询问什么输出什么即可喽~~~具体怎么推出来这个公式我是真不清楚，只会查到公式直接应用，要让我证明为什么这样可解，我实在是心有余而力不足啊！

代码

#include <iostream>

using namespace std;

const int MAXN = 1e6 + 10;
const int MOD = 1e9 + 7;

int n;
int f[MAXN] = {
  1, 1};

void init()
{
    for (int i = 2; i < MAXN; i++)
    {
        if (i % 2)
        {
            f[i] = f[i - 1];
        }
        else
        {
            f[i] = (f[i - 1] + f[i >> 1]) % MOD;
        }
    }
}

int main(int argc, const char * argv[])
{
    init();

    while (cin >> n)
    {
        cout << f[n] << '\n';
    }

    return 0;
}