Funcia
Lv.4divide-and-conquerfftmathntt

Multiplying Large Polynomials

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

Two polynomials are given by their coefficient arrays (a[i] is the coefficient of xix^i). Return the coefficients of C(x)=A(x)⋅B(x)C(x) = A(x) \cdot B(x) modulo 998,244,353, from x0x^0 upward. The result always has length a.length + b.length - 1 (zero coefficients are kept).

Examples

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

Example 1 — (1+2x)(3+4x)=3+10x+8x2(1 + 2x)(3 + 4x) = 3 + 10x + 8x^2.

Example 2 — 998,244,352≡−1998{,}244{,}352 \equiv -1, so the product is 1−x31 - x^3.

Example 3 — low-order zero coefficients stay in the result.

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

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

Constraints

  • 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

Expected complexity

Time
O(N log N)
Space
O(N)

Examples

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

Hint

Hint

Schoolbook multiplication is O(NM)O(NM). Instead evaluate both polynomials at the dd-th roots of unity (dd a power of two ≥\ge a.length + b.length - 1), multiply pointwise, and interpolate back; divide and conquer on even/odd terms makes both transforms O(dlog⁡d)O(d \log d). Because 998,244,353=119⋅223+1998{,}244{,}353 = 119 \cdot 2^{23} + 1 is prime with primitive root 33, exact integer roots of unity exist modulo it, so use the number-theoretic transform (multiply by d−1d^{-1} after the inverse transform). The schoolbook method exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.133370 msderived
Java 251520 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4011verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.