require 'mathn'
require './poly1'
 
max = 201
n = 10
 
C = Array.new( max + 1 ) { Array.new( max + 1 ) { 0 } }
A = Array.new( max ) { Array.new( max ) { 0 } }
T = Array.new( max ) { [] }
P = Array.new( max )
 
t1 = Time.now()
 
# C[k][j] : 二項係数
C[0][0] = 1
for k in 1..max
  C[k][0] = C[k-1][0]
  for j in 1..k
    C[k][j] = C[k-1][j-1] + C[k-1][j]
  end
end
 
# A[k][j] : 冪和係数
A[0][0] = 1
T[0].push( 1, 0 )
for k in 1...max
  A[k][0] = C[k+1][0] / ( k + 1 )
  T[k].push( A[k][0] )
  for j in 1..k
    A[k][j] = C[k+1][j]
    for s in 0...j
      A[k][j] = A[k][j] - C[k+1][k-j+s] * A[k-j+s][s]
    end
    A[k][j] = A[k][j] / ( k + 1 )
    T[k].push( A[k][j] )
  end
  T[k].push( 0 )
end
 
# P[k] : 冪和多項式
for k in 0...max
  P[k] = Poly1( T[k].reverse )
end
 
printf "P_{%d}(%d) =\n", max - 1, n
printf "%d\n", P[max-1].Horner( n )
t2 = Time.now()
printf "time = %d[sec]\n", t2 - t1

require 'mathn'
require './poly1'
 
max = 201
n = 10
 
A = Array.new( max + 2 ) { [] }
B = Array.new( max + 1 ) { 0 }
P = Array.new( max )
 
t1 = Time.now()
 
# A[k][j] : 二項係数
A[0].push( 1 )
for k in 1..(max+1)
  for j in 0..k
    if j == 0
      A[k].push( A[k-1][0] )
    elsif j < k
      A[k].push( A[k-1][j-1] + A[k-1][j] )
    else
      A[k].push( A[k-1][j-1])
    end
  end
end
 
# B[j] : ベルヌーイ数
B[0] = 1
for j in 1..max
  B[j] = A[j+1][j]
  for s in 0...j
    B[j] -= A[j+1][s] * B[s]
  end
  B[j] /= ( j + 1 )
end
 
# A[k][j] *=  B[j]
for k in 0..max
  for j in 0...A[k].length
    A[k][j] *= B[j]
  end
  A[k][A[k].length-1] = 0
end
 
# P[k] : k次冪和多項式
for k in 0...max
  P[k] = Poly1( A[k+1].reverse ) / ( k + 1 )
end
 
printf "P_{%d}(%d) =\n", max - 1, n
printf "%d\n", P[max-1].Horner( n )
t2 = Time.now()
printf "time = %d[sec]\n", t2 - t1