|
||||||||||
Math ClassTime Limit: 18000/9000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 203 Accepted Submission(s): 44 Problem Description Now it's time after math class! The teacher taught Baby Volcano what can do with polynomials and how to use polynomials.The teacher said that a polynomial of degree $n$ can be written as $f(x)=\sum \limits_{i=0}^{n} a_i x^i$. Also,you can regard it as a function,and replace $x$ with some number $a$ in order to get a special value called $f(a)$ Today's math homework is to calculate $f(a)$ of a polynomial of degree $n$,$f(x)$.Because the answer is extremely large,Baby Volcano is only asked to write $f(x) \bmod p$ on the paper,where $p$ is a prime number. Baby Volcano writes number $f(0) \bmod p,f(1) \bmod p,\cdots,f(n) \bmod p$ on a textbook quickly. After a while,however,he lost $f(x)$ and can't continue with his homework. Baby Volcano want to find $f(x)$,But he is too small to solve it.Baby Volcano needs your help! Input The first line contains one integer $T(1 \le T \le 50)$ stand for the test cases you should solve. For each test cases,the first line contains two integer $n,p(1 \leq n < p-1,3 \leq p \leq 5 \times 10^5)$. The next line contains $n+1$ integer,the $i$-th stand for $f(i-1)$. The input garantees that $\sum p \leq 10^6,p$ is prime,$0 \leq f(i) < p$. Output For each test case, you should firstly output "Case #t: "(without quotes), where $t$ is the index of this test case. In the next line,you should output a single line contains $n+1$ integer.The $i$-th stands for $a_{i-1} \bmod p$. It can be proved that there is only one solution if you modulo the coefficient by $p$,so there is and only one acceptable output. Sample Input
Sample Output
Source | ||||||||||
|