PKU 2229: Sumsets

よい子の味方！動的計画法！
ナップサック問題ですよー！

long long型や剰余は計算時間が長いので、使わないほうが良いらしいです.お気をつけて！

#include <stdio.h>
#include <string.h>

int main(void)
{
    int i, j;
    int num;
    static int ans[1000001];
    
    scanf("%d", &num);
    
    ans[0] = 1;
    
    for (i = 1; i <= num; i *= 2){
        for (j = 0; j + i <= num; j++){
            ans[j + i] += ans[j];
            if (ans[j + i] >= 1000000000){
                ans[j + i] -= 1000000000;
            }
        }
    }
    
    printf("%d\n", ans[num]);
    
    return (0);
}