BTCODE_E - Recover Polynomials

no tags 

Venkatesh is an expert in mathematics, and loves playing around with polynomials during his free time. His favourite mathematical equation is pretty obviously: f(x) = an*xn + an-1*xn-1 + ..... + a1*x + a0. His friend Suhash loves posing challenges to Venkatesh. Once they were discussing a particular problem at Snacky, which goes as follows:

Suhash would choose an integer 'n' as the degree of the polynomial and give Venkatesh the value of the polynomial at 'n+1' equally spaced points, i.e he gives Venkatesh integers 'n', 'x0', 'd' and g0, g1, g2, ..., gn such that: f(x0) = g0, f(x0+d) = g1, f(x0+2*d) = g2, ......f(x0+n*d) = gn. Now, Venkatesh is required to find the polynomial. Since he hates floating point values, he decides to find the polynomial in coefficient form, modulo a prime number. Can you help Venkatesh find the polynomial?


The first line of input contains an integer 't', denoting the number of test cases.
For each test case, the first line contains 3 space separated integers 'n', 'x0', 'd'. The next line contains 'n+1' space separated integers g0, g1, g2,


For each test case output 'n+1' integers, denoting the coefficients of the polynomial a0, a1, a2,...... an. All the coefficients that are printed should be non-negative and should be less than 1000000007.

You are required to find coefficients of the polynomial a0, a1, a2,...... an, which satisfy the equations: f(x0)%1000000007 = g0, f(x0+d)%1000000007 = g1, ....... f(x0+n*d)%1000000007 = gn. It is guarenteed that there is a unique solution for every test case.


3 1 1
10 26 58 112

4 3 2 1

t <= 25
1 <= n <= 1000
0 <= x0 <= 100000
0 < d  <= 10000
0 <= gi <= 10^9


Test case 1: It can be seen that the polynomial f(x) = x3 + 2*x2 + 3*x + 4 satisfies the above input.

hide comments
(Tjandra Satria Gunawan)(曾毅昆): 2014-01-02 04:40:28

Nevermind :P

(Tjandra Satria Gunawan)(曾毅昆): 2012-08-09 17:04:02

Whaa.... Gauss-Jordan elimination is TLE! Is there any faster algorithm than that? Tell me what is it?

Added by:suhash
Time limit:2.090s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Bytecode 2011, NIT Trichy, India