yukicoder-42

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#!html
<script type="text/x-mathjax-config">MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}});</script>
<script type="text/javascript" async src="http://10.71.10.90/sfiction/tool/MathJax/MathJax-master/MathJax.js?config=TeX-MML-AM_CHTML"></script>
<style>
.input, pre {
    display: block;
    padding: 9.5px;
    margin: 0 0 10px;
    font-size: 13px;
    line-height: 1.42857143;
    color: #333;
    word-break: break-all;
    word-wrap: break-word;
    background-color: #f5f5f5;
    border: 1px solid #ccc;
    border-radius: 4px;
}
</style>
}}}

== [https://yukicoder.me/problems/no/42 No.42 貯金箱の溜息] ==

=== Description ===

{{{
#!html
<p>有$6$种货币，面值分别是$1,5,10,50,100,500$。每种货币都有无限个，问有多少种方式能够组成$M$元。方案数对$10^9+9$取模。两种方案不同当且仅当存在一种货币使用的个数不同。</p>
}}}

=== Input ===

{{{
#!html
<p class="input">
$T$<br>
$M_1$<br>
$M_2$<br>
$\vdots$<br>
$M_T$
</p>
<p>
$1 \le T \le 10000, 1 \le M_i \le 10^{18}$。
</p>
}}}

=== Output ===

{{{
#!html
<p>对于每组数据，输出方案数对$10^9+9$取模。</p>
}}}

=== Sample ===

==== Sample 1 ====
输入
{{{
#!html
<pre>
4
10
100
1000000000
1000000000000000000
</pre>
}}}
输出
{{{
#!html
<pre>
4
159
248167937
266325766
</pre>
}}}

No.42 貯金箱の溜息

Description

有$6$种货币，面值分别是$1,5,10,50,100,500$。每种货币都有无限个，问有多少种方式能够组成$M$元。方案数对$10^9+9$取模。两种方案不同当且仅当存在一种货币使用的个数不同。

Input

$T$
$M_1$
$M_2$
$\vdots$
$M_T$

$1 \le T \le 10000, 1 \le M_i \le 10^{18}$。

Output

对于每组数据，输出方案数对$10^9+9$取模。

Sample

Sample 1

输入

41010010000000001000000000000000000

输出

4159248167937266325766