Funcia
Lv.4divide-and-conquerfftmathntt

큰 다항식의 곱셈

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

두 다항식의 계수가 배열로 주어집니다. a[i]는 xix^i의 계수입니다.

A(x)=∑iaixi,B(x)=∑jbjxjA(x) = \sum_{i} a_i x^i, \qquad B(x) = \sum_{j} b_j x^j

곱 C(x)=A(x)⋅B(x)C(x) = A(x) \cdot B(x)의 계수를 998,244,353으로 나눈 나머지로 구해, x0x^0부터 차례로 담은 배열을 반환하세요. 결과 배열의 길이는 항상 a.length + b.length - 1입니다(앞뒤의 0 계수도 그대로 둡니다).

입출력 예

abresult
[1, 2][3, 4][3, 10, 8]
[1, 1, 1][1, 998244352][1, 0, 0, 998244352]
[5][0, 0, 7][0, 0, 35]

입출력 예 설명

예 1 — (1+2x)(3+4x)=3+10x+8x2(1 + 2x)(3 + 4x) = 3 + 10x + 8x^2입니다.

예 2 — 998,244,352≡−1998{,}244{,}352 \equiv -1이므로 (1+x+x2)(1−x)=1−x3(1 + x + x^2)(1 - x) = 1 - x^3이고, −1-1은 998,244,352998{,}244{,}352로 나타냅니다.

예 3 — 5⋅7x2=35x25 \cdot 7x^2 = 35x^2입니다. 낮은 차수의 0 계수도 결과에 포함됩니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(a: int[], b: int[]) → int[]

제한 사항

  • 1≤1 \le a.length, b.length ≤100,000\le 100{,}000
  • 0≤0 \le a[i], b[i] <998,244,353< 998{,}244{,}353

기대 복잡도

시간
O(N log N)
공간
O(N)

입출력 예

ab기대 출력
[1,2][3,4][3,10,8]
[1,1,1][1,998244352][1,0,0,998244352]
[5][0,0,7][0,0,35]

힌트

힌트

모든 쌍을 곱하는 방법은 O(NM)O(NM)으로, 길이가 10510^5이면 101010^{10}번의 곱셈이 필요합니다.

값 표현으로 바꿔서 곱하기

차수가 dd 미만인 다항식은 서로 다른 dd개 점에서의 값으로 완전히 정해집니다. 값 표현에서는 곱셈이 점별 곱 O(d)O(d)이므로,

  1. AA, BB를 d≥d \ge a.length + b.length - 1개 점에서 평가하고,
  2. 점별로 곱한 뒤,
  3. 다시 계수로 되돌리면 됩니다(보간).

점을 1의 거듭제곱근 ω0,ω1,…,ωd−1\omega^0, \omega^1, \dots, \omega^{d-1}로 고르면 평가와 보간을 분할 정복으로 O(dlog⁡d)O(d \log d)에 할 수 있습니다(FFT). 짝수 차수 항과 홀수 차수 항으로 나누면 A(x)=Aeven(x2)+x⋅Aodd(x2)A(x) = A_{\text{even}}(x^2) + x \cdot A_{\text{odd}}(x^2)이고, ω2\omega^2는 다시 크기 d/2d/2의 1의 거듭제곱근이 되기 때문입니다.

NTT

998,244,353=119⋅223+1998{,}244{,}353 = 119 \cdot 2^{23} + 1은 소수이고 원시근이 33입니다. 그래서 이 수를 법으로 하면 길이 2232^{23}까지의 정수 1의 거듭제곱근이 존재해, 실수 오차 없이 FFT를 할 수 있습니다(수론적 변환, NTT). dd는 2의 거듭제곱으로 맞추고, 역변환 뒤에는 d−1d^{-1}을 곱합니다.

복잡도 목표

O((N+M)log⁡(N+M))O((N + M) \log (N + M))입니다. 모든 쌍을 곱하는 풀이는 효율성 테스트에서 시간 초과가 납니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.133370 ms도출됨
Java 251520 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4011판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.