200301(2)

Ruby


フーリエ変換による畳み込みを用いた多項式の乗算(2)

フーリエ変換による畳み込みを用いないで、普通に計算してみた。

# 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

def A(k, n)
  ary = []
  x = [1]
  a = [1] * k
  (n + 1).times{|i|
    ary << x
    x = mul(x, a, k * (i + 1))
  }
  ary.flatten
end

def B(k, n)
  ary = []
  x = [1]
  a = (1..k).to_a
  (n + 1).times{|i|
    ary << x
    x = mul(x, a, k * (i + 1))
  }
  ary.flatten
end

def A329708(n)
  ary = []
  (0..n).each{|i|
    a = (1..i + 1).to_a
    ary << mul(a, a, 2 * i)
  }
  ary.flatten
end

(1..5).each{|i| p A(i, 10)}
(1..5).each{|i| p B(i, 10)}
p A329708(10)

出力結果
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[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, 1, 1, 1, 1, 1, 2, 3, 4, 3, 2, 1, 1, 3, 6, 10, 12, 12, 10, 6, 3, 1, 1, 4, 10, 20, 31, 40, 44, 40, 31, 20, 10, 4, 1, 1, 5, 15, 35, 65, 101, 135, 155, 155, 135, 101, 65, 35, 15, 5, 1, 1, 6, 21, 56, 120, 216, 336, 456, 546, 580, 546, 456, 336, 216, 120, 56, 21, 6, 1, 1, 7, 28, 84, 203, 413, 728, 1128, 1554, 1918, 2128, 2128, 1918, 1554, 1128, 728, 413, 203, 84, 28, 7, 1, 1, 8, 36, 120, 322, 728, 1428, 2472, 3823, 5328, 6728, 7728, 8092, 7728, 6728, 5328, 3823, 2472, 1428, 728, 322, 120, 36, 8, 1, 1, 9, 45, 165, 486, 1206, 2598, 4950, 8451, 13051, 18351, 23607, 27876, 30276, 30276, 27876, 23607, 18351, 13051, 8451, 4950, 2598, 1206, 486, 165, 45, 9, 1, 1, 10, 55, 220, 705, 1902, 4455, 9240, 17205, 29050, 44803, 63460, 82885, 100110, 112035, 116304, 112035, 100110, 82885, 63460, 44803, 29050, 17205, 9240, 4455, 1902, 705, 220, 55, 10, 1]
[1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 4, 3, 2, 1, 1, 3, 6, 10, 15, 18, 19, 18, 15, 10, 6, 3, 1, 1, 4, 10, 20, 35, 52, 68, 80, 85, 80, 68, 52, 35, 20, 10, 4, 1, 1, 5, 15, 35, 70, 121, 185, 255, 320, 365, 381, 365, 320, 255, 185, 121, 70, 35, 15, 5, 1, 1, 6, 21, 56, 126, 246, 426, 666, 951, 1246, 1506, 1686, 1751, 1686, 1506, 1246, 951, 666, 426, 246, 126, 56, 21, 6, 1, 1, 7, 28, 84, 210, 455, 875, 1520, 2415, 3535, 4795, 6055, 7140, 7875, 8135, 7875, 7140, 6055, 4795, 3535, 2415, 1520, 875, 455, 210, 84, 28, 7, 1, 1, 8, 36, 120, 330, 784, 1652, 3144, 5475, 8800, 13140, 18320, 23940, 29400, 34000, 37080, 38165, 37080, 34000, 29400, 23940, 18320, 13140, 8800, 5475, 3144, 1652, 784, 330, 120, 36, 8, 1, 1, 9, 45, 165, 495, 1278, 2922, 6030, 11385, 19855, 32211, 48879, 69675, 93600, 118800, 142740, 162585, 175725, 180325, 175725, 162585, 142740, 118800, 93600, 69675, 48879, 32211, 19855, 11385, 6030, 2922, 1278, 495, 165, 45, 9, 1, 1, 10, 55, 220, 715, 1992, 4905, 10890, 22110, 41470, 72403, 118360, 182005, 264220, 363165, 473694, 587400, 693450, 780175, 837100, 856945, 837100, 780175, 693450, 587400, 473694, 363165, 264220, 182005, 118360, 72403, 41470, 22110, 10890, 4905, 1992, 715, 220, 55, 10, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 2, 1, 4, 4, 1, 6, 12, 8, 1, 8, 24, 32, 16, 1, 10, 40, 80, 80, 32, 1, 12, 60, 160, 240, 192, 64, 1, 14, 84, 280, 560, 672, 448, 128, 1, 16, 112, 448, 1120, 1792, 1792, 1024, 256, 1, 18, 144, 672, 2016, 4032, 5376, 4608, 2304, 512, 1, 20, 180, 960, 3360, 8064, 13440, 15360, 11520, 5120, 1024]
[1, 1, 2, 3, 1, 4, 10, 12, 9, 1, 6, 21, 44, 63, 54, 27, 1, 8, 36, 104, 214, 312, 324, 216, 81, 1, 10, 55, 200, 530, 1052, 1590, 1800, 1485, 810, 243, 1, 12, 78, 340, 1095, 2712, 5284, 8136, 9855, 9180, 6318, 2916, 729, 1, 14, 105, 532, 2009, 5922, 13993, 26840, 41979, 53298, 54243, 43092, 25515, 10206, 2187, 1, 16, 136, 784, 3388, 11536, 31864, 72592, 137638, 217776, 286776, 311472, 274428, 190512, 99144, 34992, 6561, 1, 18, 171, 1104, 5364, 20664, 65100, 170928, 378414, 710828, 1135242, 1538352, 1757700, 1673784, 1303452, 804816, 373977, 118098, 19683, 1, 20, 210, 1500, 8085, 34704, 122520, 363120, 915570, 1980440, 3692140, 5941320, 8240130, 9804240, 9924120, 8433072, 5893965, 3280500, 1377810, 393660, 59049]
[1, 1, 2, 3, 4, 1, 4, 10, 20, 25, 24, 16, 1, 6, 21, 56, 111, 174, 219, 204, 144, 64, 1, 8, 36, 120, 310, 648, 1124, 1608, 1905, 1840, 1376, 768, 256, 1, 10, 55, 220, 690, 1772, 3830, 7040, 11085, 14970, 17203, 16660, 13280, 8320, 3840, 1024, 1, 12, 78, 364, 1335, 4032, 10324, 22776, 43743, 73580, 108558, 140316, 158089, 153672, 126960, 86784, 46848, 18432, 4096, 1, 14, 105, 560, 2345, 8106, 23849, 60860, 136395, 270690, 478051, 753144, 1058715, 1325030, 1469835, 1434076, 1215984, 880320, 528640, 250880, 86016, 16384, 1, 16, 136, 816, 3836, 14896, 49336, 142256, 362086, 821456, 1672056, 3066896, 5081916, 7614096, 10308616, 12583696, 13793761, 13493856, 11673536, 8813056, 5694976, 3055616, 1294336, 393216, 65536, 1, 18, 171, 1140, 5940, 25560, 93900, 300960, 854190, 2169740, 4970250, 10323720, 19517700, 33666840, 53050140, 76370880, 100343385, 120066930, 130377315, 127816740, 112317120, 87578880, 59742720, 34928640, 16957440, 6488064, 1769472, 262144, 1, 20, 210, 1540, 8805, 41544, 167400, 589200, 1840050, 5156600, 13076140, 30190200, 63754850, 123554400, 220231800, 361542480, 546902925, 762066900, 977024850, 1150145700, 1239350265, 1217172600, 1083118800, 866419200, 616358400, 384159744, 205332480, 91095040, 31784960, 7864320, 1048576]
[1, 1, 2, 3, 4, 5, 1, 4, 10, 20, 35, 44, 46, 40, 25, 1, 6, 21, 56, 126, 234, 369, 504, 594, 574, 465, 300, 125, 1, 8, 36, 120, 330, 768, 1544, 2728, 4275, 5920, 7256, 7848, 7386, 5880, 3900, 2000, 625, 1, 10, 55, 220, 715, 1972, 4730, 10040, 19085, 32670, 50553, 70860, 89905, 102820, 105490, 96224, 76775, 52250, 29375, 12500, 3125, 1, 12, 78, 364, 1365, 4332, 11974, 29376, 64818, 129740, 236958, 396516, 609389, 860772, 1117050, 1329584, 1446498, 1430532, 1276546, 1016220, 709125, 422500, 206250, 75000, 15625, 1, 14, 105, 560, 2380, 8526, 26579, 73600, 183645, 417060, 868266, 1665804, 2956345, 4865630, 7437615, 10566136, 13946849, 17084340, 19380690, 20294820, 19525821, 17148254, 13626235, 9672600, 6020000, 3193750, 1378125, 437500, 78125, 1, 16, 136, 816, 3876, 15456, 53536, 164656, 456586, 1154096, 2680616, 5756096, 11479216, 21334096, 37042456, 60192656, 91636211, 130755056, 174842536, 218927296, 256329136, 280028816, 284582936, 267947216, 232466026, 184497760, 132647200, 85218000, 47962500, 22950000, 8875000, 2500000, 390625, 1, 18, 171, 1140, 5985, 26280, 100020, 337680, 1027710, 2852660, 7284870, 17229240, 37932570, 78053760, 150575760, 272977200, 465881355, 749445750, 1137244185, 1628385660, 2199912615, 2802614400, 3363549840, 3797152560, 4023870210, 3991747284, 3693744342, 3173605864, 2516661270, 1827606600, 1202770500, 707040000, 363628125, 158531250, 55546875, 14062500, 1953125, 1, 20, 210, 1540, 8855, 42444, 175950, 646200, 2138175, 6452600, 17924140, 46156200, 110794850, 249009400, 525822300, 1046166480, 1965440925, 3492711900, 5878567350, 9379622700, 14195606265, 20383802100, 27768280050, 35873674200, 43918845525, 50898216744, 55755208980, 57617580040, 56031446210, 51115460520, 43571112676, 34530075200, 25279752375, 16956022500, 10305506250, 5590462500, 2648984375, 1060937500, 339843750, 78125000, 9765625]
[1, 1, 4, 4, 1, 4, 10, 12, 9, 1, 4, 10, 20, 25, 24, 16, 1, 4, 10, 20, 35, 44, 46, 40, 25, 1, 4, 10, 20, 35, 56, 70, 76, 73, 60, 36, 1, 4, 10, 20, 35, 56, 84, 104, 115, 116, 106, 84, 49, 1, 4, 10, 20, 35, 56, 84, 120, 147, 164, 170, 164, 145, 112, 64, 1, 4, 10, 20, 35, 56, 84, 120, 165, 200, 224, 236, 235, 220, 190, 144, 81, 1, 4, 10, 20, 35, 56, 84, 120, 165, 220, 264, 296, 315, 320, 310, 284, 241, 180, 100, 1, 4, 10, 20, 35, 56, 84, 120, 165, 220, 286, 340, 381, 408, 420, 416, 395, 356, 298, 220, 121]