「タワー・ビルディング」問題

「タワー・ビルディング」問題

締め切りが 2018/01/04 10:00 AM なので，その 1 分後に投稿されるように予約

設問

A を一辺が 1 の立方体のブロックとし、B を縦が 1、横が 1、高さが 2 の直方体のブロックとします。
（下は横から見た図です。）
 
自然数 n, a, b に対し、A を最大 a 個、B を最大 b 個使って、縦が 1、横が 1、高さが n の直方体の塔を作ります。
このときの積み上げ方の場合の数を F(n, a, b) と定義します。
 
例えば F(6, 4, 2)＝11 です。以下に示します。

同様に、F(4, 3, 1)＝3, F(4, 4, 4)＝5, F(5, 2, 1)＝0, F(10, 5, 3)＝35 です。
また、F(100, 50, 50) を 1000003 で割った余りは 765461 となることが確かめられます。
 
標準入力から、自然数 n, a, b（1 ≦ n ≦ 500, 0 ≦ a ≦ n, 0 ≦ b ≦ n）が半角空白区切りで与えられます。
標準出力に F(n, a, b) を 1000003 で割った余りを出力するプログラムを書いてください。
 
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

n, a, b が小さいときの解を図のようにまとめれば，規則性が見える（二項係数である）

i, j は x の添え字

そこで，以下のようにプログラムすれば，爆速である。

f = function(n, a, b) {
  n1 = n + 1
  n2 = n + 2
  x = matrix(0, n1, n2)
  for (i in 1:n1) {
    x[i, i+1] = 1
  }
  for (i in 3:n1) {
    for (j in seq(3-i%%2, i-1, by=2)) {
      x[i,j] = (x[i-1, j-1]+x[i-2, j]) %% 1000003
    }
  }
  count = 0
  for (j in 2:n2) {
    if (a >= j-2 && b >= (n-j+2) %/% 2) {
      count = (count+x[n+1,j]) %% 1000003
    }
  }
  cat(count, "\n")
}

#arg = scan(file("stdin", "r"), sep=" ")
#f(arg[1], arg[2], arg[3])

f(6, 4, 2) # 11
f(100, 50, 50) # 765461
f(7, 5, 2) # 16
f(29, 10, 10) # 92378
f(500, 249, 125) # 0
f(123, 81, 82) # 475012
f(436, 400, 212) # 544100
f(497, 490, 399) # 663760