한 줄로 늘어선 표본점
다이아몬드 I의견: 0
차수가 \(N\) 미만인 다항식 $$ P(x) = c_0 + c_1 x + c_2 x^2 + \cdots + c_{N-1} x^{N-1} $$ 의 계수 \(c_0, c_1, \dots, c_{N-1}\) 이 모두 \(998244353\) 로 나눈 나머지로 주어진다.
이제 \(M\) 개의 서로 다를 수도, 같을 수도 있는 평가점 \(x_1, x_2, \dots, x_M\) 이 주어진다. 각 \(x_j\) 에 대해 \(P(x_j) \bmod 998244353\) 을 구하여라.
모든 입력값은 이미 \(998244353\) 으로 나눈 나머지로 주어진다.
\(1 \le N \le 60{,}000\)
\(1 \le M \le 60{,}000\)
\(0 \le c_i < 998244353\)
\(0 \le x_j < 998244353\)
첫 줄에 두 정수 \(N\) 과 \(M\) 이 주어진다.
둘째 줄에 \(N\) 개의 정수 \(c_0, c_1, \dots, c_{N-1}\) 이 공백으로 구분되어 주어진다.
셋째 줄에 \(M\) 개의 정수 \(x_1, x_2, \dots, x_M\) 이 공백으로 구분되어 주어진다.
한 줄에 \(M\) 개의 정수를, \(P(x_1), P(x_2), \dots, P(x_M)\) 의 순서로 공백으로 구분하여 출력한다. 각 값은 \(998244353\) 으로 나눈 나머지이다.
3 4
2 3 1
0 1 2 5
2 6 12 42\(P(x)=2+3x+x^2\). \(P(0)=2\), \(P(1)=6\), \(P(2)=12\), \(P(5)=42\).
4 3
5 0 0 7
3 3 10
194 194 7005\(P(x)=5+7x^3\). \(P(3)=5+7\cdot27=194\), 같은 점 \(P(3)=194\), \(P(10)=5+7000=7005\).
riseoj 작성
출처 Original
평가 및 의견
한 줄로 늘어선 표본점
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
한 줄로 늘어선 표본점