160221(4)

Ruby


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

DP の方が速い。
オンライン整数列大辞典の
A063865（http://oeis.org/A063865/list）
と比較し、答え合わせしてみる。

=begin
1～nまでの和がn(n + 1) / 2なので、
1～nの中からいくつか選び、和がn(n + 1) / 4
となるものを数えればよい。
=end
 
def A063865(n)
  ary = [1]
  m = n * (n + 1) / 4
  a = Array.new(m + 1){0}
  a[0] = 1
  (1..n).each{|i|
    b = a.clone
    (0..[(i - 1) * i / 2, m - i].min).each{|k| b[k + i] += a[k]}
    a = b
    i * (i + 1) % 4 == 0 ? ary << a[i * (i + 1) / 4] : ary << 0
  }
  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