POLTOPOL  Polynomial f(x) to Polynomial h(x)
Given polynomial of degree d, f(x)=c_{0}+c_{1}x+c_{2}x^{2}+c_{3}x^{3}+...+c_{d}x^{d}
For each polynomial f(x) there exists polynomial g(x) such that:
> f(x)=g(x)g(x1) for each integer x
> g(0)=0
Your task is to calculate polynomial h(x)=g(x)/x
(Note : degree of polynomial h(x) = degree of polynomial f(x))
Input
The first line of input contain an integer T, T is number of test cases (0<T≤10^{4})
Each test case consist of 2 lines:
 First line of the test case contain an integer d, d is degree of polynomial f(x) (0≤d≤18)
 Next line contains d+1 integers c_{0},c_{1},...,c_{d}, separated by space, represent the coefficient of polynomial f(x) (2^{31}<c_{0},c_{1},...,c_{d}<2^{31} and c_{d}≠0)
Output
For each test case, output the coefficient of polynomial h(x) separated by space. Each coefficient of polynomial h(x) is guaranteed to be an integer.
Example
Input: 5
0
13
1
1 2
1
0 2
2
2 5 9
3
23 9 21 104 Output: 13
0 1
1 1
1 2 3
31 41 59 26

Explanation for the first test case :
f(x)=13
g(x) that satisfy: g(x)g(x1)=f(x)=13 and g(0)=0 is: g(x)=13x
h(x)=g(x)/x so h(x)=13
output : 13
Explanation for the second test case :
f(x)=1+2x
g(x) that satisfy: g(x)g(x1)=f(x)=1+2x and g(0)=0 is: g(x)=x^{2}
h(x)=g(x)/x so h(x)=x=0+1x
output : 0 1
Explanation for the third test case :
f(x)=0+2x
g(x) that satisfy: g(x)g(x1)=f(x)=2x and g(0)=0 is: g(x)=x+x^{2}
h(x)=g(x)/x so h(x)=1+1x
output : 1 1

hide comments
Francky:
20141210 07:44:23
That's fine, it's now challenging with Python language.


(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20141210 02:54:21
I can't increase the test case because for T=10^4 the file IO size is already ~1.32MB, it's large because for each test case has at most 19 32bit numbers, so if I increase number of testcase to 10^5 theoritically the file IO will be ~13.2MB. So I decided to just rejudge this problem. This problem isn't challenging for speed anymore since the cluster changed to cube. Sorry for the inconvenience. 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20141123 12:11:26
@Francky: Done, I forgot to check "Include All Languages" when I publish this problem long time ago. Thanks for reminding me :)


Francky:
20141123 12:08:02
@tjandra : please open to all languages, I think at PY3.4 ;) 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20141123 12:08:02
@Francky: As I said before, your new code doesn't handle negative output..


Francky:
20141123 12:08:02
I still waiting for a counter example if you can. I'm unable to found one between my AC one and my WA one ???? Thanks in advance. 

Francky:
20141123 12:08:02
Hi Tjandra, thanks for your reply, but if you take a look at #11069295 AC submission, you will see that I'm still very curious about the reason of my WA.


Francky:
20141123 12:08:02
Hi Tjandra, I've yet an AC in Py2.7, but I can't understand why my new py3 code fail. I've compared over 10^5 polynomials my two near solutions, and they match.


sarelfeniel:
20141123 12:08:02
Awesome problem. Experimented with many ways to solve it but am content with top 5. 

Shashi Kant Prasad:
20141123 12:08:02
Mine: O(d²) 
Added by:  Tjandra Satria Gunawan 
Date:  20120526 
Time limit:  3s 
Source limit:  20000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Own Problem 