SPOJ.com - Problem POLTOPOL

POLTOPOL - Polynomial f(x) to Polynomial h(x)

no tags

Given polynomial of degree d, f(x) = c₀ + c₁x + c₂x² + c₃x³ + ... + c_dx^d

For each polynomial f(x) there exists polynomial g(x) such that:

f(x) = g(x) - g(x - 1) 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⁴)

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₀, c₁ ... c_d, separated by space, represent the coefficient of polynomial f(x) (-2³¹ < c₀, c₁ ... c_d < 2³¹ 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

First Test Case

f(x) = 13
g(x) that satisfy: g(x) - g(x - 1) = f(x) = 13 and g(0) = 0 is: g(x) = 13x
h(x) = g(x)/x so h(x) = 13
output : 13

Second Test Case

f(x) = -1 + 2x
g(x) that satisfy: g(x) - g(x - 1) = f(x) = -1 + 2x and g(0) = 0 is: g(x) = x²
h(x) = g(x) / x so h(x) = x = 0 + 1x
output : 0 1

Third Test Case

f(x) = 0 + 2x
g(x) that satisfy: g(x) - g(x - 1) = f(x) = 2x and g(0) = 0 is: g(x) = x + x²
h(x) = g(x) / x so h(x) = 1 + 1x
output : 1 1

Submit solution!

hide comments

< Previous 1 2 Next >

	Francky: 2014-12-10 07:44:23 That's fine, it's now challenging with Python language. Welcome to Tjandra as EB. Congratulations. Nice job for your new bot ; you always have good ideas.
	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2014-12-10 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 32-bit 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)(æ›¾æ¯…æ˜†): 2014-11-23 12:11:26 @Francky: Done, I forgot to check "Include All Languages" when I publish this problem long time ago. Thanks for reminding me :-) --ans--> Thanks, it seems cluster is now cube (and before Pyramid, isn't it ?) ans that solutions hadn't been rejudged yet. Maybe you could set new time limit to 3s... (?) as you want ; before this hypothetical rejudge. Or better, add another input file with more data (increase T to 10^5, but not d_max). What do you think about that? Ans(Tjandra): I changed time limit to 3s for now. I'll upload more test case and rejudge later (probably next week), now I'm not in my home city. Last edit: 2014-11-23 13:44:01
	Francky: 2014-11-23 12:08:02 @tjandra : please open to all languages, I think at PY3.4 ;-)
	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2014-11-23 12:08:02 @Francky: As I said before, your new code doesn't handle negative output.. But I still don't know why your assertion is pass (AC), I'm curious too why python assertion fail.. But this is the fact, my output test data contains many negative number.. --ans(Francky)--> OK, so it's a spoj bug or feature on assert, I tried a division by 0 instead and can see the red light. Thanks for your patience with me. I have at last my green light in C, and I'll try the 0.06s !!! (edit, done ;-) Last edit: 2014-02-28 20:11:25
	Francky: 2014-11-23 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: 2014-11-23 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. Ans: Try this: assert ((0<=Q[i]) and (Q[i]<231-1)) --ans(Francky)--> Done, I'm still very curious ;-) Ans: Now you make me curious too :-P Ok, I'll tell you when I know why. Last edit: 2014-02-16 21:41:34
	Francky: 2014-11-23 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. Please test my sub_10998183. Thanks. I'm very curious about that. Ans: It's simple, you forgot to handle negative output :) I recommend test your code on ideone, because the engine is same with SPOJ. Last edit: 2014-02-09 22:52:39
	sarelfeniel: 2014-11-23 12:08:02 Awesome problem. Experimented with many ways to solve it but am content with top 5.
	Shashi Kant Prasad: 2014-11-23 12:08:02 Mine: O(d²)

Submit solution!

Added by:	Tjandra Satria Gunawan
Date:	2012-05-26
Time limit:	3s
Source limit:	20000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All
Resource:	Own Problem