当初の締め切りが 2/18 10:00AM なので，その 1 分後に投稿されるように予約する
自然数 n に対して、次の等式を考えます。
□1□2□3□4…□n ＝ 0
四角の部分には、プラス（＋）またはマイナス（－）の記号が入ります。
等式を成立させるような記号の入れ方を考えましょう。
例えば、n = 7 のとき、次の 8 通りの入れ方が可能です。
＋1＋2－3＋4－5－6＋7 ＝ 0
＋1＋2－3－4＋5＋6－7 ＝ 0
＋1－2＋3＋4－5＋6－7 ＝ 0
＋1－2－3－4－5＋6＋7 ＝ 0
－1＋2＋3＋4＋5－6－7 ＝ 0
－1＋2－3－4＋5－6＋7 ＝ 0
－1－2＋3＋4－5－6＋7 ＝ 0
－1－2＋3－4＋5＋6－7 ＝ 0
自然数 n に対し、等式を成立させる記号の入れ方の数を F(n) と定義します。例えば F(7) = 8 です。
同様に、F(3) = 2、F(8) = 14 となることが確かめられます。
標準入力から、自然数 n （1 ≦ n ≦ 50）が与えられます。
標準出力に F(n) の値を出力するプログラムを書いてください。
f = function(n, s) { # f(n, 0) で求まる
if (n == 0) s == 0
else if (abs(s) > n*(n+1)/2) 0
else Recall(n-1, s-n) + Recall(n-1, s+n)
}
> f(3,0)
[1] 2
> f(7,0)
[1] 8
> f(8,0)
[1] 14
しかし，これでは，n = 50 なんてことになると，いつまで待っても答が返ってこない
そこで，以下のプログラムにする
瞬殺である
g = function(n) {
d = 1
for (m in 1:(n+1)) {
len = length(d)
i = ceiling(len/2)
a = ifelse(i > len, 0, d[i])
e = c(rep(0, 2*m), d)
d = e+rev(e)
}
a
}
> options(digits=16)
> g(3)
[1] 2
> g(7)
[1] 8
> g(8)
[1] 14
> g(48)
[1] 1140994231458
> g(49)
[1] 0
gawk で --bignum を指定して
$ cat a.awk
function f(n) {
len = 1
d[len] = 1
for (m = 1; n+1 >= m; m++) {
i = int((len+1)/2)
a = i > len ? 0 : d[i]
for (j = 1; 2*m >= j; j++) {
e[j] = 0
}
for (j = 1; len >= j; j++) {
e[j+2*m] = d[j]
}
len += 2*m
for (j = 1; len >= j; j++) {
d[j] = e[j]+e[len+1-j]
}
}
print a
}
BEGIN{
f(48)
f(100)
f(101)
f(102)
f(103)
}
$ gawk --bignum --file=a.awk
1140994231458
1731024005948725016633786324
0
0
13252206944539668255309614628
