Lv.4divide-and-conquerfftmathntt
큰 다항식의 곱셈
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
두 다항식의 계수가 배열로 주어집니다. a[i]는 의 계수입니다.
곱 의 계수를 998,244,353으로 나눈 나머지로 구해, 부터 차례로 담은 배열을 반환하세요. 결과 배열의 길이는 항상 a.length + b.length - 1입니다(앞뒤의 0 계수도 그대로 둡니다).
입출력 예
| a | b | result |
|---|---|---|
[1, 2] | [3, 4] | [3, 10, 8] |
[1, 1, 1] | [1, 998244352] | [1, 0, 0, 998244352] |
[5] | [0, 0, 7] | [0, 0, 35] |
입출력 예 설명
예 1 — 입니다.
예 2 — 이므로 이고, 은 로 나타냅니다.
예 3 — 입니다. 낮은 차수의 0 계수도 결과에 포함됩니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(a: int[], b: int[]) → int[]
제한 사항
-
a.length,b.length -
a[i],b[i]
기대 복잡도
- 시간
- O(N log N)
- 공간
- O(N)
입출력 예
| a | b | 기대 출력 |
|---|---|---|
[1,2] | [3,4] | [3,10,8] |
[1,1,1] | [1,998244352] | [1,0,0,998244352] |
[5] | [0,0,7] | [0,0,35] |
힌트
힌트
모든 쌍을 곱하는 방법은 으로, 길이가 이면 번의 곱셈이 필요합니다.
값 표현으로 바꿔서 곱하기
차수가 미만인 다항식은 서로 다른 개 점에서의 값으로 완전히 정해집니다. 값 표현에서는 곱셈이 점별 곱 이므로,
- , 를
a.length + b.length - 1개 점에서 평가하고, - 점별로 곱한 뒤,
- 다시 계수로 되돌리면 됩니다(보간).
점을 1의 거듭제곱근 로 고르면 평가와 보간을 분할 정복으로 에 할 수 있습니다(FFT). 짝수 차수 항과 홀수 차수 항으로 나누면 이고, 는 다시 크기 의 1의 거듭제곱근이 되기 때문입니다.
NTT
은 소수이고 원시근이 입니다. 그래서 이 수를 법으로 하면 길이 까지의 정수 1의 거듭제곱근이 존재해, 실수 오차 없이 FFT를 할 수 있습니다(수론적 변환, NTT). 는 2의 거듭제곱으로 맞추고, 역변환 뒤에는 을 곱합니다.
복잡도 목표
입니다. 모든 쌍을 곱하는 풀이는 효율성 테스트에서 시간 초과가 납니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 3370 ms | 도출됨 |
| Java 25 | 1520 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 11 | 판정만 |
| performance | 60 | 4 | 판정만 |