ADVANCED ALGORITHMS - DIVIDE & CONQUER:FFT Animations

def multiply_polynomials_naive(A, B):
    """Naive polynomial multiplication: O(n²)"""
    n, m = len(A), len(B)
    result = [0] * (n + m - 1)
    
    for i in range(n):
        for j in range(m):
            result[i + j] += A[i] * B[j]
    
    return result

import math
import cmath

def fft(poly, inverse=False):
    """
    Fast Fourier Transform.
    Time: O(n log n)
    """
    n = len(poly)
    
    # Base case
    if n == 1:
        return poly
    
    # Divide: Split into even and odd
    even = fft(poly[0::2], inverse)
    odd = fft(poly[1::2], inverse)
    
    # Combine
    result = [0] * n
    angle = 2 * math.pi / n
    if inverse:
        angle = -angle
    
    for i in range(n // 2):
        twiddle = cmath.exp(1j * angle * i)
        result[i] = even[i] + twiddle * odd[i]
        result[i + n // 2] = even[i] - twiddle * odd[i]
    
    if inverse:
        result = [x / n for x in result]
    
    return result

def ifft(poly):
    """Inverse FFT"""
    return fft(poly, inverse=True)

def multiply_polynomials_fft(A, B):
    """Multiply polynomials using FFT: O(n log n)"""
    # Pad to power of 2
    n = 1
    while n < len(A) + len(B):
        n <<= 1
    
    A_padded = A + [0] * (n - len(A))
    B_padded = B + [0] * (n - len(B))
    
    # FFT
    A_fft = fft(A_padded)
    B_fft = fft(B_padded)
    
    # Point-wise multiplication
    C_fft = [A_fft[i] * B_fft[i] for i in range(n)]
    
    # Inverse FFT
    C = ifft(C_fft)
    
    # Round to integers
    return [round(x.real) for x in C[:len(A) + len(B) - 1]]