BOJ 2410:: 2의 멱수의 합

$n$의 제한이 1,000,000인데, 2¹⁹ < 1,000,000 < 2²⁰이므로 1, 2, 4, …, 2¹⁹으로 $n$을 나타내는 방법의 수를 물어보는 것과 동일합니다. $m$을 아래와 같이 정의합시다.

최종적으로 구해야 하는 건 $m[n][19]$입니다.

점화식을 생각해봅시다. 1, 2, 4, …, 2^$j$으로 $n$을 나타낼 때 2^$j$을 전혀 안 쓸 수도 있고 적어도 한 번 쓸 수도 있습니다. 따라서 다음 관게가 성립합니다.

단, $i$가 2^$j$보다 작으면 $m[i][j] = m[i][j-1]$입니다. 또한 $i$가 0이면 방법의 수는 1가지이고 $j$가 0이면 1만 쓸 수 있으므로 방법의 수는 역시 1가지입니다.

#include<cstdio>

using namespace std;

int m[1000001][20];

int main(void) {
    int n;
    scanf("%d", &n);

    for (int i = 0; i < 20; i++)
        m[0][i] = 1;

    for (int i = 1; i <= n; i++) {
        m[i][0] = 1;
        for (int j = 1; j < 20; j++) {
            if (i >= (1 << j))
                m[i][j] = (m[i][j - 1] + m[i - (1 << j)][j]) % 1000000000;
            else
                m[i][j] = m[i][j - 1];
        }
    }

    printf("%d", m[n][19]);

    return 0;
}