結果

問題 No.41 貯金箱の溜息（EASY）
コンテスト
ユーザー data9824
提出日時 2015-06-16 04:44:56
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 21 ms / 5,000 ms
コード長 971 bytes
コンパイル時間 444 ms
コンパイル使用メモリ 54,620 KB
実行使用メモリ 11,140 KB
最終ジャッジ日時 2024-07-06 21:39:42
合計ジャッジ時間 868 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>

using namespace std;

const long long MOD = 1000000009LL;
const int COIN_TYPES = 10;
const long long COINS[1 + COIN_TYPES] = { 
	0, 
	1, 
	111111 / 111111, 
	222222 / 111111, 
	333333 / 111111, 
	444444 / 111111,
	555555 / 111111, 
	666666 / 111111, 
	777777 / 111111, 
	888888 / 111111, 
	999999 / 111111
};
const long long MAX_NUMBER = 10000000000LL / 111111L;
long long patterns[1 + COIN_TYPES][1 + MAX_NUMBER];

int main() {
	patterns[0][0] = 1;
	for (int k = 1; k <= MAX_NUMBER; ++k) {
		patterns[0][k] = 0;
	}
	for (int i = 1; i <= COIN_TYPES; ++i) {
		patterns[i][0] = 1;
		for (int k = 1; k <= MAX_NUMBER; ++k) {
			patterns[i][k] = patterns[i - 1][k];
			if (k - COINS[i] >= 0) {
				patterns[i][k] += patterns[i][k - COINS[i]];
				patterns[i][k] %= MOD;
			}
		}
	}
	int t;
	cin >> t;
	for (int i = 0; i < t; ++i) {
		long long m;
		cin >> m;
		m = m - m % 111111;
		m /= 111111;
		cout << patterns[COIN_TYPES][m] << endl;
	}
	return 0;
}
0