201016

Crystal


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

以下を用いて、n が4000 のときの値を求めることはおすすめしない。

require "big"

def a063865(n)
  ary = [1.to_big_i]
  m = n * (n + 1) // 4
  a = Array.new(m + 1){0.to_big_i}
  a[0] = 1.to_big_i
  (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.to_big_i
  }
  ary
end

p a063865(1000)[-1]

出力結果

467708586991053780130476928496471502490480200263913521598374850751872554493810444457551220080062611698129340084492921358002542871554381676735263500063986630523649271451391806356678763700553308953903873511563867155215734010997332808966175771715884247295296277348179194597363883854664431808932677416