### PROBLEM LINK:

**Author:** Konstantsin Sokol

**Tester:** Gedi Zheng

**Editorialist:** Miguel Oliveira

### DIFFICULTY:

Hard.

### PREREQUISITES:

Math, Linear Algebra.

### PROBLEM

Given 2 polynomials Q and T, find a polynomial P such that P(x) = Q(x) + \int_0^1 T(x \cdot s) P(s) ds holds for every real x.

### EXPLANATION

We are given polynomials Q and T, and the formula P(x) = Q(x) + \int_0^1 T(x \cdot s) P(s) ds.

Q(x) = \sum\limits_{k=0}^n q_k x^k and T(x \cdot s) = \sum\limits_{k=0}^m t_k \cdot x^k \cdot s^k

Thus, P(x) = Q(x) + \int_0^1 T(x \cdot s) P(s) ds = \sum\limits_{k=0}^n q_k x^k + \int_0^1 (\sum\limits_{k=0}^m t_k \cdot x^k \cdot s^k) P(s) ds

P(x) = \sum\limits_{k=0}^n q_k * x^k + \sum\limits_{k=0}^m t_k \cdot x^k * (\int_0^1 s^k P(s) ds)

Notice that \int_0^1 s^k P(s) ds is a constant for each x. Letâ€™s call this c_x. Then, P(x) = \sum\limits_{k=0}^n q_k x^k + \sum\limits_{k=0}^m t_k x^k \cdot c_x

Now we are interested in finding all c_1, c_2, ..., c_m.

c_i = \int_0^1 s^i P(s) ds = \int_0^1 s^i (\sum\limits_{k=0}^n q_k s^k + \sum\limits_{k=0}^m t_k s^k \cdot c_x) ds

c_i = \sum\limits_{k=0}^n q_k \cdot \int_0^1 s^{k+i} ds + \sum\limits_{k=0}^m c_k \cdot t_k \int_0^1 s^{k+i} ds, note that \int_0^1 s^{k+i} ds = \frac{1}{k+i+1}

Then we have c_i = \sum\limits_{k=0}^n q_k \cdot \frac{1}{k+i+1} + \sum\limits_{k=0}^m c_k \cdot \frac{t_k}{k+i+1}

Thus, we have m equations and m variables. We can build a system of equations and use the gaussian elimination method to solve the system and calculate the coefficients.

**Time Complexity**

Building the system of equations will take O(N) time and the gauss elimination O(M^3), thus giving O(N + M^3) total time.