Chef and Equations

All submissions for this problem are available.
###Read problems statements [Hindi](http://www.codechef.com/download/translated/NOV18/hindi/CHEFEQUA.pdf) , [Vietnamese](http://www.codechef.com/download/translated/NOV18/vietnamese/CHEFEQUA.pdf) , [Mandarin Chinese](http://www.codechef.com/download/translated/NOV18/mandarin/CHEFEQUA.pdf) , [Russian](http://www.codechef.com/download/translated/NOV18/russian/CHEFEQUA.pdf) and [Bengali](http://www.codechef.com/download/translated/NOV18/bengali/CHEFEQUA.pdf) as well. You are given a sequence of positive integers $A_0, A_1, \ldots, A_{N1}$ and a sequence of nonnegative integers $C_0, C_1, \ldots, C_{N1}$. Let's denote $M = 998244353$. You know that for $$C_i = \sum_{j = 0}^{N1} B_j A_j^i \mod M$$ holds for each valid $i$, with some coefficients $B_0, B_1, \dots, B_{N1}$ (such that $0 \le B_i \lt M$ for each $i$). Your task is to find these coefficients. It is possible to prove that under the given constraints, the solution is unique. ### Input  The first line of the input contains a single integer $N$.  The second line contains $N$ spaceseparated integers $A_0, A_1, \ldots, A_{N1}$.  The third line contains $N$ spaceseparated integers $C_0, C_1, \ldots, C_{N1}$. ### Output Print a single line containing $N$ spaceseparated integers $B_0, B_1, \ldots, B_{N1}$. ###Constraints  $1 \le N \le 60,000$  $1 \le A_i \lt M$ for each valid $i$  $0 \le C_i \lt M$ for each valid $i$  $A_i \neq A_j$ for each valid $i, j$ ($i \neq j$) ### Subtasks **Subtask #1 (5 points):** $1 \le N \le 300$ **Subtask #2 (15 points):** $1 \le N \le 3,000$ **Subtask #3 (20 points):** $C_i = C_1^i\;\mathrm{mod}\;M$ for each valid $i$ **Subtask #4 (60 points):** original constraints ### Example Input ``` 3 1 2 3 3 6 14 ``` ### Example Output ``` 1 1 1 ``` ### Explanation The relations between $A$, $B$ and $C$ hold:  $C_0 = 3 = 1^0 + 2^0 + 3^0$  $C_1 = 6 = 1^1 + 2^1 + 3^1$  $C_2 = 14 = 1^2 + 2^2 + 3^2$Author:  wxh010910 
Tags  divideandconq, generating_functions, interpolation, mediumhard, nov18, ntt, taran_1407, wxh010910 
Date Added:  12092018 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions