全員が楽しめるファミリーレストラン

全員が楽しめるファミリーレストラン

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

設問
大人数でファミリーレストランに行ったとき、複数のテーブルに分かれて座ることにしました。
このとき、1人だけのテーブルを作ることがないように分けます。
例えば、6人の場合、以下の4通りがあります。
・2人＋2人＋2人
・2人＋4人
・3人＋3人
・6人
1つのテーブルに配置できる最大の人数が m 人のとき、
n 人が1つ以上のテーブルに分かれて座る人数のパターンを求めます。
（人数のパターンだけを求め、誰がどのテーブルに座るかは考えないものとします。）
m, n が標準入力からスペース区切りで与えられるとき、
このパターン数を標準出力に出力してください。
なお、m, n は 2≦m≦12、2≦n≦1000 を満たす整数とします。

【入出力サンプル】
標準入力
6 6

標準出力
4

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

この問題は「整数分割」であるが， 2 以上の数で分割するという条件が付く
「オンライン整数列大辞典」にもあるが，m = 12 のような場合には，数列生成法については記述がない
いつものように，m, n の小さいところで解を求めて，行列表示して規則性を探る
個別の m について漸化式を求めようとすると項数が多くなるし，m が大きくなると重回帰分析を応用するという方法では解が求まらなくなる
図をつらつら眺めて，若干の試行錯誤をすると，この行列は以下のように構成できることがわかった



1. n × m 行列を作る（結果的には，1000×12 の行列を作っても，計算時間は微々たるものだとわかるが）
2. m = 2 の列は，n が偶数なら 1，奇数なら 0 なので，a[n, 1] = n %% 2 == 0
3. m = 3 〜 m = 12 の最初の m 個の要素は (0, 1, 1, 2, 2, 4, 4, 7, 8, 12, 14, 21) の先頭から m 個（水色の部分）
4. m 列の m+1 行以降は a[i, m] = a[i, m-1]+a[i-m, m], i >= m+1
 m = 12, n = 30 のとき，a[30, 12] = a[30, 11] + a[18, 12] = 665+81 = 746
 m = 12, n = 987 すなわち，a[987, 12] = 738331156658280 も瞬時に求まる

f = function(m0, n0) {
    tbl = matrix(0, 1000,  12)
    tbl[1:12,] = c(0,1,1,2,2,4,4,7,8,12,14,21)
    tbl[,2] = 0:1
    for (m in 3:12) {
        for (n in (m+1):1000) {
            tbl[n, m] = tbl[n, m-1] + tbl[n-m, m]
        }
    }
    options(scipen=100)
    cat(tbl[n0, m0])
}

f(6, 6) # 4
f(2, 10) # 1
f(5, 20) # 28
f(6, 1000) # 60220121
f(12, 987) # 738331156658280

再帰関数としても書けるが，このままでは実用的ではない

f = function(m, n) {
    if (m == 2) {
        (n %% 2 == 0) + 0
    } else if (n <= m) {
        c(0,1,1,2,2,4,4,7,8,12,14,21)[n]
    } else {
        f(m-1,n)+f(m, n-m)
    }
}

f(7, 11) # 11
f(12, 30) # 746
f(12, 100) # 1312646 かなり時間が掛かる
f(6, 6) # 4
f(2, 10) # 1
f(5, 20) # 28