OMC079(D)

　他の問題のwriterだったので，writer権限でtesterもやっていたのですが，そのときに思いついた解法を紹介します．

　便宜上，$0$ も増加的な数とする．以下のように定義する：

• 集合 $A,B$ に対して，$A$ の要素であるが，$B$ の要素でないもの全体の集合を $A\setminus B$ と表す．
• 有限集合 $C$ に対して，$C$ の持つ元の個数を $\lvert C\rvert$ と表し，その $\lvert C\rvert$ 個の元の総和を $S(C)$ と表す．
• $K=1,2,\ldots,9$ に対して，集合 $Z_{K}$ を $1$ の位が $K$ 以下である増加的な数全体で定める．

　いま，増加的な数は集合 $\lbrace 1,2,\ldots,9 \rbrace$ の部分集合と一対一に対応することから，$\lvert Z_{K}\rvert =2^K$ である．さらに，定義より，$9$ 以下の正の整数 $a,b$ に対して，$a \lt b \iff Z_{a}\subset Z_{b}$ が成立することに留意せよ．いま求めたいものは $S(Z_{9})$ と表せる．
　$K \geq 2$ を固定して集合 $Z_{K}\setminus Z_{K-1}$ の元 $M$ について考察してみよう．$M$ は増加的な数であるから，$M$ の末尾 $1$ 桁を取り除いた数 $\dfrac{M-K}{10}$ も増加的な数であり，その $1$ の位は $K-1$ 以下であるので，$\dfrac{M-K}{10} \in Z_{K-1}$ である．$\lvert Z_{K}\setminus Z_{K-1}\rvert=\lvert Z_{K-1}\rvert$ であることより，$\dfrac{M-K}{10}$ として考えられる数全体の集合が $Z_{K-1}$ と一致するので， $$S(Z_{K}\setminus Z_{K-1})=10S(Z_{K-1})+K\lvert Z_{K-1}\rvert=10S(Z_{K-1})+K2^{K-1}$$ である．このことから，$S(Z_{K})=11S(Z_{K-1})+K2^{K-1}$ がわかる．$S(Z_{1})=1$ であるから，得られた式を繰り返し用いて計算することで（筆者はここでOMC電卓を用いた），$S(Z_{9})=\bm{320214537}$ であることがわかる．

【補足1】ここで得られた $S(Z_{K})=11S(Z_{K-1})+K2^{K-1}$ という漸化式を解いて $K$ に対する一般項を得ることもできるが，$sum(Z_{9})$ を求められさえすればそれでいい本題では，それをする旨味はほとんどない．

【補足2】提出するべき値は，$123456789×511 \lt 10^9×10^3=10^{12}$ より $10^{12}$ 未満であるので，OMC電卓であれば余裕をもって表示することができる．したがってOMC電卓を用いて $511$ 個の整数を足し合わせることでも正解を得られるはずである．