My Solution (100pts)
Since the sequence C is not really restricted to have only N elements, I made a generating function for it. What you get is:
\displaystyle C_0 + C_1x + C_2x^2 \ldots = \sum_{i=0}^{N-1} B_i(1 + A_ix + A_i^2x^2 + \ldots) = \sum_{i=0}^{N-1} \frac{B_i}{1-A_ix}
\displaystyle \text{Now let } Q(x) = \prod_{i=0}^{N-1}(1-A_ix)
If I multiply Q to both sides of this, on the right I get a polynomial of degree N-1 i.e. N coeffients.
Since the first N coefficients of the product depend only on the first N coefficients of the 2 polynomials being multiplied, I can write the right side as \displaystyle \frac{P(x)}{Q(x)} where P(x) = The first N coefficients of \displaystyle (C_0 + C_1x + C_2x^2 \ldots + C_{N-1}x^{N-1})Q(x)
\displaystyle \therefore \frac{P(x)}{(1-A_1x)(1-A_2x)\ldots(1-A_{N-1}x)} = \frac{B_1}{1-A_1x} + \frac{B_2}{1-A_2x} \ldots \frac{B_{N-1}}{1-A_{N-1}x}
This is a partial fraction decomposition and the solution is given by \displaystyle B_i = -A_i\frac{P\left(\frac{1}{A_i}\right)}{Q'\left(\frac{1}{A_i}\right)} where Q' is the derivative of Q (cover up method).
If we further let P^*(x) = x^{N-1}P\left(\frac{1}{x}\right) i.e. the polynomial we get by reversing the coefficient list of P and similarly Q^*(x) = -x^{N-1}Q'(\frac{1}{x}) we get
\displaystyle B_i = A_i\frac{P^*(A_i)}{Q^*(A_i)}
We can find out the values of P^* and Q^* at any N points in O(N\log^2 N) using the algorithm described here.
An example in case anyone doesn’t get it. I’ll be using the sample test case for this.
Q(x) = (1-x)(1-2x)(1-3x) = 1-6x+11x^2-6x^3
P(x) = \text{First 3 coefficients of } (3+6x+14x^2)(1-6x+11x^2-6x^3) = 3 - 12x + 11x^2
P^* (x) = 11-12x+3x^2
Q'(x) = -6 + 22x - 18x^2
Q^* (x) = 18 - 22x + 6x^2
\therefore B_0, B_1, B_2 = \text{value of } \displaystyle x\frac{11-12x+3x^2}{18-22x+6x^2} \text{ at } x=1,2,3 \text{ respectively.}