POJ 3181 Dollar Dayz

3181 -- Dollar Dayz

　最近予定が合わなくてコンテストの方はちっとも出れていないのですが引き続き蟻本の練習問題です。

問題概要

1..K円のコインでN円を作るときの場合の数

解法

dp[i][j] := i円以下のコインでj円をつくるときの場合の数
とすると
dp[i][j] = if j < i dp[i - 1][j] else dp[i - 1][j] + dp[i][j - i]
です。
sum(dp[i - 1][j - hoge](0 <= hoge <= i))がdp[i][j - 1]になるのを利用しています。詳しくは蟻本59pを。

で。
この問題なんと最大ケースの答えが15658181104580771094597751280645なので多倍長が必要です。
＋＝だけあればいいし正負も関係ない、と思って適当に実装して通しましたが、普通にクソ問だと思います。

#include <cstdio>
#include <vector>
using namespace std;

struct bigint {
    typedef long long i64;
    static const i64 BASE = 1.0e17;
    vector<i64> data;
    bigint() {}
    bigint (i64 x) {
        for(; x > 0; x /= BASE) data.push_back(x % BASE);
    }
    bigint& operator += (const bigint& x) {
        if(data.size() < x.data.size()) data.resize(x.data.size());
        i64 tmp = 0LL;
        for(int i = 0; i < data.size(); ++i) {
            data[i] += (i < x.data.size() ? x.data[i] : 0) + tmp;
            tmp = data[i] / BASE;
            data[i] %= BASE;
        }
        if(tmp) data.push_back(1LL);
        return *this;
    }
    void print() {
        for(int i = data.size() - 1; i >= 0; --i) {
            if(i == data.size() - 1) printf("%lld", data[i]);
            else printf("%016lld", data[i]);
        }
        printf("\n");
    }
};
int main() {
    int N, K; scanf("%d%d", &N, &K);
    vector<bigint> dp(N + 1, 0);
    dp[0] = 1LL;
    for(int k = 1; k <= K; ++k)
      for(int n = k; n <= N; ++n)
        dp[n] += dp[n - k];
    dp[N].print();
    return 0;
}

時間あったらbigintのもっとちゃんとしたやつを作りたい気もしますが、割り算とか面倒そうだしあんまりやりたくないかも……。
そもそも競技じゃなければboostを使えばいい話ですしね。