From Matrix Exponentiation to Kitamasa Method

--- Hi, I'm AmirMohammad (commonly known as Danet). Naturally, as a non-native speaker, the translation and editing process involved some assistance. If you spot any technical or linguistic errors, I would be grateful if you pointed them out!

Faster Computation of Linear Recurrence DP

Problem Statement

We are given a linear recurrence relation of order ( k ):

Along with the first ( k ) values:

Our goal is to compute ( dp[n] ) efficiently for very large ( n ).

Classical Solution: Matrix Exponentiation

State Definition

To compute the recurrence, we always need the last ( k ) values. So we define the state vector as:

This vector fully describes the DP state at step ( i ).

Transition Rule There exists a fixed matrix ( M ) such that:

Applying this transition repeatedly:

So the problem reduces to exponentiating a matrix.

Transition Matrix The transition matrix has the following form:

• The first row applies the recurrence
• The remaining rows only shift values downward

Time Complexity

This is correct but becomes too slow when ( k ) is large.

Key Observation

We do not actually need the entire matrix ( M^n ).

Important facts: - Only the first row affects ( dp[n] ) - All other rows are pure shifts - The transition itself is linear and fixed

This suggests that the problem can be solved without matrices.

Shift Operator Interpretation Introduce a symbolic operator ( x ) that represents one DP transition.

Interpretation:

So: - ( x ) behaves exactly like applying the recurrence once - ( x^n ) means applying the recurrence ( n ) times

This operator plays the same role as the matrix ( M ), but algebraically.

Characteristic Polynomial From the recurrence:

Replace ( dp[i] ) with powers of ( x ):

Move everything to the left-hand side:

Define the characteristic polynomial:

This polynomial encodes the recurrence completely.

Main Idea of Kitamasa Method

We want to compute ( x^n ).

Using polynomial division:

Taking modulo ( p(x) ):

Where:

So the remainder can be written as:

Mapping this back to DP:

Conclusion:
Computing ( dp[n] ) is equivalent to computing
( x^n \bmod p(x) ).

Fibonacci Example

Consider Fibonacci numbers:

Here ( k = 2 ), and the characteristic polynomial is:

Which implies:

Computing f(3):

Therefore:

Computing f(4):

Thus:

---

Binary Exponentiation on Polynomials

Assume we already know:

To compute (x^(2n)):

Steps: 1. Multiply two polynomials of degree ( < k ) 2. Reduce the result modulo p(x).

Each step costs O(k^2).

Final Complexity

Using FFT: