记录
16:29 2023-5-26
http://poj.org/problem?id=2229
reference:《挑战程序设计竞赛(第2版)》第二章练习题索引 p135
这个问题是https://oeis.org/A018819 Binary partition function: number of partitions of n into powers of 2.
找到的比较简单的证明:https://www.quora.com/How-can-I-find-the-number-of-ways-to-decompose-any-number-in-powers-of-two-algorithm-code-dynamic-programming
找到个比较有意思的网站:https://oeis.org/
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAX_N 1000000
#define moder 1000000000
typedef long long ll;
typedef unsigned int uint;
const int INF = 0x3f3f3f3f;
ll N;
ll dp[MAX_N + 1];
//查了公式
//a(2m+1) = a(2m), a(2m) = a(2m-1) + a(m)
void solve() {
dp[0] = 1;
for(ll i = 1; i <= N; i++) {
if(i % 2 == 1) {
dp[i] = dp[i - 1] % moder;
} else {
dp[i] = dp[i - 1] + dp[i / 2] % moder;
}
}
printf("%lld\n", dp[N]);
// printf("%lld\n", dp[N]);
}
int main() {
scanf("%d", &N);
solve();
}