170528

Ruby


一変数多項式の0乗

ずっと以下のコードの前者を使っていたが、
OEIS のSquare Array が元になっている数列を求めるときは、
後者を使う方が便利なときがある。

# m次以下を取り出す
def mul(f_ary, b_ary, m)
  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[0..m]
end

# m次以下を取り出す
def power0(ary, n, m)
  return [1] if n == 0
  k = power0(ary, n >> 1, m)
  k = mul(k, k, m)
  return k if n & 1 == 0
  return mul(k, ary, m)
end

# m次以下を取り出す
def power1(ary, n, m)
  if n == 0
    a = Array.new(m + 1, 0)
    a[0] = 1
    return a
  end
  k = power1(ary, n >> 1, m)
  k = mul(k, k, m)
  return k if n & 1 == 0
  return mul(k, ary, m)
end

m = 20
n = 10
ary = [1, 1]
(0..n).each{|i| p power0(ary, i, m)}
p ""
(0..n).each{|i| p power1(ary, i, m)}
p ""
# power0のように使うことも可能
(0..n).each{|i| p power1(ary, i, i)}
p ""
ary = [1, 1, 1]
(0..n).each{|i| p power0(ary, i, m)}
p ""
(0..n).each{|i| p power1(ary, i, m)}
p ""
# power0のように使うことも可能
(0..n).each{|i| p power1(ary, i, i * 2)}

出力結果
[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]
[1, 6, 15, 20, 15, 6, 1]
[1, 7, 21, 35, 35, 21, 7, 1]
[1, 8, 28, 56, 70, 56, 28, 8, 1]
[1, 9, 36, 84, 126, 126, 84, 36, 9, 1]
[1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1]
""
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 3, 3, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 4, 6, 4, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 5, 10, 10, 5, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 6, 15, 20, 15, 6, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 7, 21, 35, 35, 21, 7, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 8, 28, 56, 70, 56, 28, 8, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 9, 36, 84, 126, 126, 84, 36, 9, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
""
[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]
[1, 6, 15, 20, 15, 6, 1]
[1, 7, 21, 35, 35, 21, 7, 1]
[1, 8, 28, 56, 70, 56, 28, 8, 1]
[1, 9, 36, 84, 126, 126, 84, 36, 9, 1]
[1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1]
""
[1]
[1, 1, 1]
[1, 2, 3, 2, 1]
[1, 3, 6, 7, 6, 3, 1]
[1, 4, 10, 16, 19, 16, 10, 4, 1]
[1, 5, 15, 30, 45, 51, 45, 30, 15, 5, 1]
[1, 6, 21, 50, 90, 126, 141, 126, 90, 50, 21, 6, 1]
[1, 7, 28, 77, 161, 266, 357, 393, 357, 266, 161, 77, 28, 7, 1]
[1, 8, 36, 112, 266, 504, 784, 1016, 1107, 1016, 784, 504, 266, 112, 36, 8, 1]
[1, 9, 45, 156, 414, 882, 1554, 2304, 2907, 3139, 2907, 2304, 1554, 882, 414, 156, 45, 9, 1]
[1, 10, 55, 210, 615, 1452, 2850, 4740, 6765, 8350, 8953, 8350, 6765, 4740, 2850, 1452, 615, 210, 55, 10, 1]
""
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 2, 3, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 3, 6, 7, 6, 3, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 4, 10, 16, 19, 16, 10, 4, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 5, 15, 30, 45, 51, 45, 30, 15, 5, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 6, 21, 50, 90, 126, 141, 126, 90, 50, 21, 6, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 7, 28, 77, 161, 266, 357, 393, 357, 266, 161, 77, 28, 7, 1, 0, 0, 0, 0, 0, 0]
[1, 8, 36, 112, 266, 504, 784, 1016, 1107, 1016, 784, 504, 266, 112, 36, 8, 1, 0, 0, 0, 0]
[1, 9, 45, 156, 414, 882, 1554, 2304, 2907, 3139, 2907, 2304, 1554, 882, 414, 156, 45, 9, 1, 0, 0]
[1, 10, 55, 210, 615, 1452, 2850, 4740, 6765, 8350, 8953, 8350, 6765, 4740, 2850, 1452, 615, 210, 55, 10, 1]
""
[1]
[1, 1, 1]
[1, 2, 3, 2, 1]
[1, 3, 6, 7, 6, 3, 1]
[1, 4, 10, 16, 19, 16, 10, 4, 1]
[1, 5, 15, 30, 45, 51, 45, 30, 15, 5, 1]
[1, 6, 21, 50, 90, 126, 141, 126, 90, 50, 21, 6, 1]
[1, 7, 28, 77, 161, 266, 357, 393, 357, 266, 161, 77, 28, 7, 1]
[1, 8, 36, 112, 266, 504, 784, 1016, 1107, 1016, 784, 504, 266, 112, 36, 8, 1]
[1, 9, 45, 156, 414, 882, 1554, 2304, 2907, 3139, 2907, 2304, 1554, 882, 414, 156, 45, 9, 1]
[1, 10, 55, 210, 615, 1452, 2850, 4740, 6765, 8350, 8953, 8350, 6765, 4740, 2850, 1452, 615, 210, 55, 10, 1]