ファミリーレストランのテーブルを配置して！

ファミリーレストランのテーブルを配置して！

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

客の人数に合わせてテーブルを動かすファミリーレストランを考えます。
例えば、1人客や2人組の客を、4人掛けのテーブルに通せば、残りの席が無駄になります。
そこで、2人掛けテーブルを組み合わせて、できるだけ効率よくテーブルを配置しています。

店内に2人掛けテーブルが m 個あり、n 人の客が店内にいるとき、テーブルの組み合わせ方として考えられるものが何通りあるか求めてみます。
このとき、どの客がどのテーブルのどこに座っているかは区別せず、テーブルの位置も区別しないものとします。
つまり、以下のような配置はいずれも同じ(1通り)とします。

なお、相席になることはないものとし、1人客でも2人掛けのテーブルを使いますし、3人客の場合は2人掛けのテーブルを2つ使います。

例えば、m = 3, n = 5 のとき、以下の4通りが考えられます。
（●…座っている人、〇…空席）

標準入力から m, n がスペース区切りで与えられるとき、テーブルの配置が何通りあるかを求め、標準出力に出力してください。
なお、m, n は 0 < m < n ≦ 80 を満たす整数とします。


【入出力サンプル】
標準入力
3 5

標準出力
4

==================================================================

整数分割法の問題であるが，m, n が大きくなると実行時間がかかる。
n が小さい部分での解を求め（図 1），規則性を探る。

この行列を各列とも，1行目から始まるように上揃えにする（図2）

各列は，1, 2, 5, 10, ... となるが，これは A000712 であるが，1行目から ceiling((j + 1)/2) 行目（水色で示したセル）までが有効。
黄緑で示したセル a[j + 1, j]，j = 1,2,3, ... は A000041[j]
赤で示したセルは a[j, j]，j = 3,4,5, ...
  a[j, j] = a[j, j-1] + a[j-1, j-1]
赤のセルの 1 つ上のセルは a[j-1, j]，j=5,6,7, ...
  a[j-1, j] = a[j-1, j-1] + a[j-3, j-2]
更にその 1 つ上のセルは a[j-2, j]，7,8,9, ...
  a[j-2, j] = a[j-2, j-1] + a[j-5, j-3]
更にその 1 つ上のセルは a[j-3, j]，9,10,11, ...
  a[j-3, j] = a[j-3, j-1] + a[j-7, j-4]
:::
となっているので，以下のプログラムを得る。

f = function(M, N) {
  m = 80

  A000203 = function(n) {
    a = integer(n)
    s = 0
    for (i in 1:n) {
      for (j in 1:i) {
        s = s + cos((2 * pi * n * j)/i)
      }
    }
    s
  }
  a000203 = sapply(1:80, A000203)

  A000041 = function(m) {
    a = integer(m)
    for (n in 1:m) {
      b = 0
      for (k in 0:(n - 1)) {
        b = b + a000203[n - k] * ifelse(k == 0, 1, a[k])
      }
      a[n] = b/n
    }
    a
  }
  a000041 = A000041(80)
 
  A000712 = function(m) {
    a = integer(m)
    for (n in 1:m) {
      b = c(1, a000041[1:(n - 1)])
      a[n] = sum(b * rev(b))
    }
    a[1] = 1
    a
  }
  a000712 = A000712(80)

  n = m + 1
  a = matrix(0, n, m)

  for (j in 1:m) {
    i = 1:ceiling((j + 1)/2)
    a[i, j] = a000712[i]
  }

  for (j in 1:m) {
    a[j + 1, j] = a000041[j]
  }

  for (k in 0:(m/2 - 2)) {
    for (j in (2 * k + 3):m) {
      a[j - k, j] = a[j - k, j - 1] + a[j - k * 2 - 1, j - k - 1]
    }
  }
  cat(a[N - M + 1, M])
}

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

system.time(f(3, 5)) # 4
system.time(f(6, 10)) # 17
system.time(f(20, 30)) # 481
system.time(f(35, 62)) # 203415
system.time(f(45, 80)) # 2086851

参考までに，図1 を得るための，n の分割による解法プログラム

initDiv = function(length, max) {
  ary = NULL
  repeat {
    if (length <= max) {
      ary = c(ary, length)
      return(ary)
    } else {
      ary = c(ary, max)
      length = length - max
    }
  }
}

nextDiv = function(ary) {
  repeat {
    sum = 0
    for (pos in length(ary):1) {
      a = ary[pos]
      sum = sum + a
      if (a != 1) {
        break
      }
    }
    if (ary[1] == 1) {
      return(FALSE)
    }
    ary = ary[1:pos]
    ary[pos] = ary[pos] - 1
    max = ary[pos]
    sum = sum - max
    pos = pos + 1
    repeat {
      if (sum <= max) {
        ary[pos] = sum
        return(ary)
      } else {
        ary[pos] = max
        sum = sum - max
      }
      pos = pos + 1
    }
  }
}

f = function(m, n) {
  first = TRUE
  count = 0
  repeat {
    if (first) {
      d = initDiv(n, n)
      first = FALSE
    } else {
      d = nextDiv(d)
      if (d[1] == FALSE) {
        break
      }
    }
      cnt = 0
      for (k in d) {
        cnt = cnt + ceiling(k / 2)
        if (cnt > m) {
          break
        }
      }
    if (cnt == m) {
      count = count + 1
    }
  }
  cat(count)
}

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

#f(3, 5) # 4
#f(6, 10) # 17
#f(20, 30) # 481
#system.time(f(35, 62)) # 203415
#system.time(f(45, 80)) # 2086851