Peking University Online Judge 2229 Sumsets

memo1[i] : 2のべき乗数による i の分割のうち、1を含む分割の個数
memo2[i] : 1を含まない分割の個数

memo1[i] は、i - 1の分割に + 1をそのまま付け加えれば全列挙できるので、memo1[i] = memo1[i - 1] + memo2[i - 1]で表される。
memo2[i] は、例えばi = 8ならば8, 4 + 4, 4 + 2 + 2, 2 + 2 + 2 + 2の4個だが、すべての項を2で割ると4, 2 + 2, 2 + 1 + 1, 1 + 1 + 1 + 1となり、これは4の分割の総数と等しくなる。よって、memo2[i] = memo1[i / 2] + memo2[i / 2](ただし、i が奇数の場合は0)

#include<cstdio>
using namespace std;
typedef long long int ll;
static const int MAX_N = 1000000;
static const ll MOD = 1000000000;

int N;
ll memo1[MAX_N + 1], memo2[MAX_N + 1];

int main(){
	scanf("%d", &N);
	memo1[1] = 1;
	for(int i = 2; i <= N; i++){
		memo1[i] = memo1[i - 1] + memo2[i - 1];
		if(i % 2 == 0) memo2[i] = memo1[i / 2] + memo2[i / 2];
		memo1[i] %= MOD;
		memo2[i] %= MOD;
	}
	printf("%lld\n", (memo1[N] + memo2[N]) % MOD);
	return 0;
}