2229:Sumsets

keyword

組合せ　動的計画法　C++

概要

整数n(<10^6)が与えられる。nを2のべき数の和で表す方法の総数を求める問題。
よくある、硬貨の組合せの問題。dp[支払う金額][使う最大の硬貨]とすると計算量O(支払う金額*硬貨の枚数)で求めることができて、この場合の硬貨の枚数は2^20>10^6だから2^0...2^19の20枚で十分。なので計算量2*10^7。ちょっと厳しいものがあるけど何とかなる範囲。1回TLEもらったけど細かいところを修正して無事AC。

int main(){
    int twos[20];
    int n, i, j;
    const int mod=1000000000;
    static int dp[1000003][20];
    scanf("%d",&n);
    REP(i,20) twos[i] = (1<<i);
    REPONE(i,n)REP(j,20) dp[i][j] = 0;
    REP(j,20)dp[0][j] = dp[1][j] = 1;
    for(i=2;i<=n;i++){
        REP(j,20){
            if((i-twos[j])>=0){
                dp[i][j] = dp[i-twos[j]][j];
            }
            else break;
        }
        REPONE(j,19)
            dp[i][j] = (dp[i][j] + dp[i][j-1])%mod;
    }
    printf("%d\n",dp[n][19]);

    return 0;
}