题解 | #整数拆分#

#include<iostream>
using namespace std;

const int MOD = 1e9;

const int N = 1000010;

int f[N];
int v[30];
int main(void)
{
	int n;
	cin >> n;
	int index = 1;
	for(int i = 1;i <= n;i *= 2) v[index++] = i;
	f[0] = 1;
	for(int i = 1;i < index;i++)
	{
		for(int j = v[i];j <= n;j++)
		{
			f[j] = (f[j] + f[j - v[i]]) % MOD;
		}
	}
	
	cout << f[n] << endl;
	
	return 0;
}