概要
最終的な結論は同じです。
解法
硬貨の価値の集合を $A = \{1,5,10,50,100,500\}$ と書きます。
多項式・形式的べき級数による解法に慣れていれば、直ちに次の問題に帰着されます：
$\displaystyle F = \prod_{a\in A} \frac{1}{1-x^a}$ とするとき、$[x^M] F$ を求めよ。
$d = 666$ 次式を分母に持つ有理式なので、$M$ 次の係数は $\Theta(d\log d\log M)$ で計算できます。しかし、これでは本問題を解くには不足です。分母の特殊性による高速化を検討します。
何となく部分分数分解 $F = \sum \frac{多項式}{1-x^a}$ といった形を目指したくもなりますが、ここまで簡単な形にはなりません。分母において $x=1$ の重複度が $6$ あるためです。ついでにいえば、$1$ の$5$乗根や $10$ 乗根も重複度があります。適切な形に部分分数分解して解くことは可能かと思いますが、ここでは別の方法を取ります。
全ての $a\in A$ が $500$ の約数であることに注目すると、$F$ はある多項式 $P$ を用いて $\displaystyle F = \frac{P}{(1-x^{500})^6}$ と書けることが分かります。
このことから、次の結論を得ることができます。$N = 500$ とおきます。
各 $0\leq r < N$ に対して、数列 $\{[x^{r+iN}] F\}$ は $i$ の $5$ 次多項式である。
証明します。$F = \frac{P}{(1-x^N)^6}$ において、$P$ の各項を次数の $N$ での剰余ごとにまとめると、$\displaystyle F = \sum_{0\leq r<N}x^r\frac{P_r(x^N)}{(1-x^N)^6}$ と書くことができます。$F_r(x) = \frac{P_r(x)}{(1-x)^6}$ とおくと、$F(x) = \sum_{r}x^rF_r(x^N)$ となります。数列 $\{[x^{r+iN}] F\}$ は数列 $\{[x^i]F_r\}$ と一致するので、$F_r$ が分母 $(1-x)^6$ を持つ有理式であることから主張が従います。
あとは $M < 3000$ を愚直に計算したあと、各 $r$ に対して $r, r+N, \ldots, r+5N$ における値から、多項式補間して $r + iN$ における値が計算できて、本問題を解くことができます。
まとめ・課題
もうちょっと一般的に上手にできる方法があれば、ぜひ教えてください。
