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; }