All Tracks Math Problem

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

Subtasks

  • 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...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

HourStorm #7

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?