PROBLEM LINK:Author: Konstantsin Sokol DIFFICULTY:Hard. PREREQUISITES:Math, Linear Algebra. PROBLEMGiven 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$. EXPLANATIONWe 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. AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 20 Apr '15, 00:56

Hello I think solving this problem in python is quite easy : I have figured out the general equation as shown above And I know that there is a module available to solve system of linear equations. And so I directly used that, Here is my solution : http://www.codechef.com/viewsolution/6799925 answered 20 Apr '15, 07:58

Yeah...the links to the solution files are not working. answered 22 May '15, 10:51
