형식적 멱급수의 역원
다이아몬드 IV의견: 0
차수가 \(n-1\) 이하인 다항식 \(A(x) = a_0 + a_1 x + \dots + a_{n-1} x^{n-1}\)이 주어진다. 계수는 모두 소수 \(p = 998{,}244{,}353\)로 나눈 나머지로 주어지며, \(a_0 \ne 0\)이다.
\(A(x) \cdot B(x) \equiv 1 \pmod{x^{n}}\)을 만족하는 다항식 \(B(x) = b_0 + b_1 x + \dots + b_{n-1} x^{n-1}\)의 계수 \(b_0, \dots, b_{n-1}\)을 모두 구하여라. 모든 계수는 \(p\)로 나눈 나머지로 출력한다.
\(n\)이 커서 \(O(n^2)\) 점화식은 통과할 수 없다.
\(1 \le n \le 200{,}000\)
\(0 \le a_i < p\)
\(a_0 \ne 0\)
첫 줄에 정수 \(n\)이 주어진다.
둘째 줄에 \(a_0, a_1, \dots, a_{n-1}\)이 공백으로 구분되어 주어진다.
한 줄에 \(b_0, b_1, \dots, b_{n-1}\)을 공백으로 구분해 출력한다.
2
1 1
1 998244352\(A(x)=1+x\)의 역원은 \(1 - x + x^2 - \dots\)이다. \(x^2\)로 자르면 \(1 - x\), 즉 \(b_0=1\), \(b_1 = p-1 = 998244352\)이다.
3
2 0 0
499122177 0 0\(A(x)=2\)는 상수이다. 역원은 \(2^{-1} \bmod p = 499122177\)이고 나머지 계수는 모두 0이다.
riseoj 작성
출처 Original
평가 및 의견
형식적 멱급수의 역원
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
형식적 멱급수의 역원