2 subtopics · 5 problems
Matrix Exponentiation & FFT
Matrix power for linear recurrences and FFT/NTT for polynomial multiplication.
01Matrix Exponentiation
Compute n-th term of a linear recurrence in O(k³ log n).
3 hard
| Problem | Difficulty | Link |
|---|---|---|
| 185APlant | hard | Solve |
| 166ETetrahedron | hard | Solve |
| 718CSasha and Array | hard | Solve |
02FFT / NTT
Multiply polynomials in O(n log n) — convolutions, counting.
2 hard
| Problem | Difficulty | Link |
|---|---|---|
| 632EThief in a Shop | hard | Solve |
| 993ENikita and Order Statistics | hard | Solve |
Was this helpful?