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.