Problem Given 2 N degree polynomials as $$a_0 + a_1x+a_2x^2+...+a_Nx^N $$ and $$b_0 + b_1x+a_2x^2+...+b_Nx^N $$
Assume no 2 coefficient are same in the 2 polynomials.
Find the product of the polynomials but the catch is that the product(*) operator between the coefficients is defined differently.
let $$ f(i,j) = a_i * b_j = \frac {1}{ \mid a_i-b_j \mid } $$
I have to find the following polynomial.
$$c_0 + c_1x+c_2x^2+...+c_{2N}x^{2N} $$
where
$$ c_k = \sum_{i=0}^N f(i,k-i) $$ I know that with FFT, 2 polynomials can be multiplied in $O(n \log n)$ time with normal product operator between the coefficients but don't have any idea for this kind of problem.
You can write this as a convolution by taking the polynomial with coefficients 1: $$ e\left(x\right)=\sum_{k=0}^{2N}x^{k} $$ and the polynomial $$ f\left(x\right)=\sum_{k=0}^{N}\frac{1}{\left|a_{k}-b_{k}\right|}x^{k} $$ and considering their convolution and applying the usual convolution theorem.