Yukicoder041 貯金箱の溜息EASY)

問題概要

$T\leqq10^4$、$M[i]\leqq10^{10}$

1円、i*111111円$(1≦i≦9)$がある。M[i]円を払う際の硬貨の組み合わせ数を$10^9+9$で割ったあまりで求めよ。 yukicoder041

解法

1円玉のみで支払うとき、すべての金額について払うことができ、ある金額については1通りしかない。 次に111111円について考える。111111円の倍数で構成される金額は、111111->1単位とみて、DPで組み合わせ数を求めることができる。 最後に端数を考える。端数については1円のみで支払うしかない。 したがってもとめるDPは、$dp[i]:=111111*i$円支払う際の組み合わせ

$SIZE=M[i]/111111として、$
計算量:$O(SIZE+T)$

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    using VI = vector<int>;       using VVI = vector<VI>;
    #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
    
    LL N;
    LL ans = 0LL;
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
    
        const LL mod = 1000000009;
        VI dp(1e5 + 10, 1);
    
        FOR(c, 1, 10) {
            FOR(i, 0, 1e5) {
                (dp[i + c] += dp[i]) %= mod;
            }
        }
    
        int T; cin >> T;
        FOR(t, 0, T) {
            LL m; cin >> m;
            ans = dp[m / 111111];
            cout << ans << "\n";
        }
    
        return 0;
    }