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; }