mayoko’s diary

プロコンとかいろいろ。

yukicoder No.41 貯金箱の溜息(EASY)

解法

1 円玉を除けば, 六並び国では 111111 円の倍数のお金しか支払うことが出来ません。よって, M 円を 111111 円で割った商を 1, 2, ..., 9 の和で何通り表すことができるか, という dp 問題にすることが出来ます。dp[i][j] = i 以下の数字を使って和を j にする方法, ですね。

dp の初期化では dp[0][0] = 1 だけでなく, 1 円玉を考慮するとすべての j について dp[0][j] = 1 が成り立つことには注意。

const ll ZORO = 111111;
const ll MAX = 10000000000ll/ZORO + 10;
const ll MOD = 1e9+9;

ll dp[11][MAX];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    for (int i = 0; i < MAX; i++) dp[0][i] = 1;
    for (int i = 1; i <= 9; i++) {
        for (int j = 0; j < MAX; j++) {
            dp[i][j] = dp[i-1][j];
            if (j-i >= 0) (dp[i][j] += dp[i][j-i]) %= MOD;;
        }
    }
    while (T--) {
        ll M;
        cin >> M;
        ll tar = M/ZORO;
        cout << dp[9][tar] << endl;
    }
    return 0;
}