Number Game
Tag(s):

Fast Fourier transform, Hard, Linear Algebra, Mathematics

Problem
Editorial
Analytics

You are given $N+1$ distinct positive integers $A_1,A_2,......,A_{N+1}$ and a positive integer $M$. A polynomial of degree $N$ is defined as follows:

$f(x)= P_1x^N + P_2x^{N-1} + ……..+ P_Nx + P_{N+1}$

such that following conditions hold true:

• $f(A_i) = A_i^{N+1} \ \forall i\in [1,N+1]$

• $P_1 > 0$

• $P_1,P_2,.....,P_{N+1}$ are integers

A new polynomial is defined as

$S(x) = X_1x^N + X_2x^{N-1} + ……..+ X_Nx + X_{N+1}$

Such that $X_i = |P_i|\%M \ \ \forall i\in [1,N+1]$ and $X_1,X_2,.......,X_{N+1}$ are integers.

Evaluate $S(0)\%M, S(1)\%M ,…….S(M-1)\%M$ .

Input format

• First line: Two space separated integers $N$ and $M$
• Second line: $N+1$ space separated integers $A_1,A_2,......,A_{N+1}$

Output format

• Output $M$ space-separated integers $S(0)\%M, S(1)\%M ,…….S(M-1)\%M$

Constraints

$1 \le N,M, A_i \le 10^5$

$M$ is prime

• For 20 Points: $1 \le N,M, A_i \le 1000$
• For 80 Points: Original constraints
SAMPLE INPUT
2 13
1 2 3
SAMPLE OUTPUT
6 10 0 2 3 3 2 0 10 6 1 8 1
Explanation

Required polynomial $F(x)$ is $6x^2 - 11x + 6$ and hence $S(x)$ is $6x^2 + 11x + 6$. Hence $S(0)\% M = 6$, $S(1)\%M = 23\%13 = 10$ and so on.

Time Limit: 4.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...

Contributor 