回答まとめはこちら

問題は下記。

1 から 4 の数字を使って作る n 桁の整数のうち、9 の倍数となるものの個数を F(n) と定義します。例えば、F(1) = F(2) = 0、F(3) = 10、F(4) = 40 となることが確かめられます。

標準入力から、自然数 n（1 ≦ n ≦ 20）が与えられます。標準出力に F(n) の値を出力するプログラムを書いてください。

1111…から4444…まで全通り生成して数えていては終わらないので、9の剰余で分類します。すなわち、１から４の数字を使って作るn桁の数字のうち、9で割ったあまりがrになるものの個数をとすると、

の漸化式になります。

これをrubyで計算し、F(n,0)を出力するコードが下記。Hashの引数が9で割ったあまりになっています。

n=gets.to_i
h={}
h[1]=h[2]=h[3]=h[4]=1
(1...n).each{|m|
  tmp=Hash.new{|h,k| h[k]=0 }
  h.each{|k,v|
    (1..4).each{|i|
      tmp[(i+k)%9]+=v
    }
  }
  h=tmp
}
puts h[0]

最近始めたschemeで書いたのはこちら、末尾再帰といえば聞こえはいいけど、ループを再帰にして、状態を関数の引数で覚えている、というだけ。もっとスマートに書けると思うんだけど、引数10個くらいだしまぁいいよね、ということで。

(use-modules (ice-9 rdelim))
(define (solve i a0 a1 a2 a3 a4 a5 a6 a7 a8)
    (if (= i 1)
        a0
        (+ (solve (- i 1)
                  (+ a5 a6 a7 a8)
                  (+ a6 a7 a8 a0)
                  (+ a7 a8 a0 a1)
                  (+ a8 a0 a1 a2)
                  (+ a0 a1 a2 a3)
                  (+ a1 a2 a3 a4)
                  (+ a2 a3 a4 a5)
                  (+ a3 a4 a5 a6)
                  (+ a4 a5 a6 a7)))))
(display (solve (string->number (read-line)) 0 1 1 1 1 0 0 0 0))
(newline)