report VI VI EN
Register | Login
  • HOME
  • PROBLEMSET
  • ROADMAP
  • COMPETITION
  • TOPIC
  • RANKING
  • GUIDE
  • MASHUP
  • ABOUT
  • CONTACT
Module Matrix multiplication

Matrix multiplication

**Frequency: 1.5/10** Matrix multiplication is _mostly_ used in competitive programming to solve DP problems with unreasonably high constraints.

Resources

- [USACO: Matrix Exponentiation](https://usaco.guide/plat/matrix-expo?lang=cpp)

Problems

Fibonacci 2 252 / 264 1500
Martian language 2 103 / 107 1500
Hakurei Shrine 2 78 / 108 1600
Number sequence 96 / 111 1700
Chess 45 / 65 1800

Data structure

  • Sweep Line
  • Introduction to Trie
  • Square root decomposition

Tree

  • Rerooting
  • Small-to-large
  • Heavy-light decomposition

Graph

  • Strongly connect component
  • Articulation point and bridge
  • Bipartite Matching

Dynamic Programming

  • Digit DP
  • Matrix multiplication

Hashing

  • Hash a set

Others

  • Divide and conquer

Geometry

  • Geometry

Binary search

  • Parallel binary search

Others

  • Additional Problems (Level 5)