160221(2)

Ruby


Number of solutions to +- 1 +- 2 +- 3 +- ... +- n = 0(1)

「プラス・マイナス・ゼロ」問題のしえるさんのコードで知った解き方を
真似して解いてみた。
オンライン整数列大辞典の
A063865（http://oeis.org/A063865/list）
と比較し、答え合わせしてみる。

def mul(f_ary, b_ary)
  s1, s2 = f_ary.size, b_ary.size
  ary = Array.new(s1 + s2 - 1, 0)
  (0..s1 - 1).each{|i|
    (0..s2 - 1).each{|j|
      ary[i + j] += f_ary[i] * b_ary[j]
    }
  }
  ary
end

def A063865(n)
  ary = [1]
  ary0 = [1]
  (1..n).each{|k|
    ary1 = Array.new(n + k + 1, 0)
    ary1[n - k] = 1
    ary1[n + k] = 1
    ary0 = mul(ary0, ary1)
    ary << ary0[k * n]
  }
  ary
end
ary = A063865(46)

# OEIS A063865のデータ
ary0 =
[1,0,0,2,2,0,0,8,14,0,0,70,124,0,0,722,1314,0,0,
 8220,15272,0,0,99820,187692,0,0,1265204,2399784,0,
 0,16547220,31592878,0,0,221653776,425363952,0,0,
 3025553180,5830034720,0,0,41931984034,81072032060,
 0,0]
# 一致の確認
p ary == ary0