class Poly
    attr_accessor :array, :limit  #系数向量，次数界
    def initialize(a)
        @array = []
        a.each {|e| @array.push Complex(e, 0)}
        [url=home.php?mod=space&uid=215071]@limit[/url] = a.size
    end
    def exchange #位逆序置换
        j = 0
        (0...@limit).each do |i|
            if j > i
                t = @array[i]
                @array[i] = @array[j]
                @array[j] = t
            end
            k = @limit
            j &= ~k while j&(k >>= 1) != 0 #倒着做减法
            j |= k
        end
    end
    PI = Math.acos(-1)
    def fft(idft = false)
        pi = PI
        pi = -pi if idft #idft旋转方向反过来
        exchange   #置换
        s = 1  #合并区间的长度
        while s < @limit
            t  = 0
            while t < @limit  #合并区间的开始点
                x = pi/s
                omgn = Complex(Math.cos(x), Math.sin(x))
                omg = Complex(1.0, 0.0)
                
                (0...s).each do |m|
                    a1 = m+t
                    a2 = m+t+s
                    Complex comm = omg * @array[a2]  #蝴蝶操作
                    @array[a2] = @array[a1] - comm
                    @array[a1] = @array[a1] + comm
                    omg = omg*omgn
                end
                
                t += s<<1
            end
            s <<= 1
        end
        @array.map!{|e| e/@limit} if idft   #逆变换
    end
    def mul(o)
        s = 1
        s <<= 1 while s < @limit + o.limit
        (@limit...s).each {|i| @array[i] = Complex(0.0, 0.0)}
        (o.limit...s).each {|i| o.array[i] = Complex(0.0, 0.0)}  #不足补零
        @limit = o.limit = s  #修正次数界
        
        fft
        o.fft
        (0...s).each do |i|
            @array[i] *= o.array[i]
        end
        fft(true)
    end
    #-----------------------
    def mul_with(poly)
        x = Poly.new(@array)
        y = Poly.new(poly.array)
        x.mul(y)
        (0...x.limit).each do |i|
            @array[i] = Integer(x.array[i].real+0.5)  #四舍五入...
        end
    end
end

#test
#多项式乘法(1+2x)(1+2x+x^2) = (1+4x+5x^2+2x^3)
#结果的多项式次数界为3，四项
x = Poly.new([1, 2])
y = Poly.new([1, 2, 1])
x.mul_with y
#输出结果的系数
#puts x.array #=> 1 4 5 2 0 0 0 0 (末尾4个0是多余的)
puts x.array[0..3]