차수가 \(N-1\) 이하인 다항식 \(A(x) = a_0 + a_1 x + a_2 x^2 + \dots + a_{N-1} x^{N-1}\)의 계수가 주어진다. 모든 계산은 소수 \(998{,}244{,}353\)으로 나눈 나머지로 한다.

정수 \(w\)와 개수 \(M\)이 주어질 때, 다음 \(M\)개의 값을 모두 구하여라:

\(A(w^0),\ A(w^1),\ A(w^2),\ \dots,\ A(w^{M-1})\) (모두 \(\bmod\ 998{,}244{,}353\)).

\(1 \le N \le 100{,}000\)

\(1 \le M \le 100{,}000\)

\(0 \le w \le 998{,}244{,}352\)

첫 줄에 세 정수 \(N\), \(M\), \(w\)가 주어진다.

둘째 줄에 \(N\)개의 정수 \(a_0, a_1, \dots, a_{N-1}\)이 공백으로 구분되어 주어진다 (각각 \(0\) 이상 \(998{,}244{,}352\) 이하).

한 줄에 \(M\)개의 값 \(A(w^0), \dots, A(w^{M-1})\)을 공백으로 구분하여 출력한다.

riseoj 작성

출처 Original