题解 | 整数拆分

一望而知的递归题，因此首先寻找规律。

显然 $1$ 可以且仅可以展开为 $1=2^0$ 。对于一个非 $1$ 正整数 $n$ ，其一定可以表示为 $(n-1)+2^0$ ，而 $2^0$ 显然无法被进一步展开，因此其展开方法数 $f(n)$ 至少应该等于 $f(n-1)$ ，即 $f(n)\ge f(n-1)$ 。若 $n$ 为奇数，则 $n$ 和 $n-1$ 的展开相比仅可能在 $n-1$ 的所有展开的基础上多出一个 $2^0$ （这是因为 $2$ 的所有整数幂中只有 $2^0=1$ 为奇数），因此 $f(2n+1)=f(2n).$ 另一方面，若 $n$ 为偶数时，其可以通过有 $f(n-1)$ 种展开的奇数 $n-1$ 加上 $2^0$ 得到，也可以通过 $\frac{n}{2}$ 的展开基础上再重复一次展开得到；因此 $f(2n)=f(n)+f(2n-1).$

据上方可知 $f(n)=\begin{cases}f(n-1) & ,n\equiv1\mod 2\\f(n-1)+f(\frac{n}{2}) & ,n\equiv 0\mod 2\end{cases}.$

#include <bits/stdc++.h>
#define _CRT_SECURE_NO_DEPRECATE

int main() {
    int n;
    std::cin >> n;
    std::vector<int> f(n + 1);
    for (int i = 1; i <= n; i++) {
        if (i == 1) f[i] = 1;
        else if (i % 2) f[i] = f[i - 1];
        else f[i] = (f[i - 1] + f[i / 2]) % 1000000000;
    }
    std::cout << f[n] % 1000000000 << std::endl;
}

若使用递归函数，代码会对大数发生栈溢造成超时，因此使用数组存储中间值。