### 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 \):↵
↵
$$↵
\begin{align}↵
dp[n] &= c_1 \cdot dp[n-1] + c_2 \cdot dp[n-2] + \dots + c_k \cdot dp[n-k]↵
\end{align}↵
$$↵
↵
Along with the first \( k \) values:↵
↵
$$↵
\begin{align}↵
dp[0],\ dp[1],\ \dots,\ dp[k-1]↵
\end{align}↵
$$↵
↵
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:↵
↵
$$↵
\begin{align}↵
V(i) &= [\, dp[i],\ dp[i-1],\ dp[i-2],\ \dots,\ dp[i-k+1] \,]↵
\end{align}↵
$$↵
↵
This vector fully describes the DP state at step \( i \).↵
↵
↵
**Transition Rule**↵
There exists a fixed matrix \( M \) such that:↵
↵
$$↵
\begin{align}↵
V(i+1) &= M \cdot V(i)↵
\end{align}↵
$$↵
↵
Applying this transition repeatedly:↵
↵
$$↵
\begin{align}↵
V(n) &= M^{\,n-k} \cdot V(k)↵
\end{align}↵
$$↵
↵
So the problem reduces to exponentiating a matrix.↵
↵
↵
**Transition Matrix**↵
The transition matrix has the following form:↵
↵
$$↵
\begin{align}↵
M &=↵
\begin{bmatrix}↵
c_1 & c_2 & \dots & c_k \\↵
1 & 0 & \dots & 0 \\↵
0 & 1 & \dots & 0 \\↵
\vdots & \vdots & \ddots & \vdots \\↵
0& 0 & \dots & 0 6 1↵
\end{bmatrix}↵
\end{align}↵
$$↵
↵
- The **first row** applies the recurrence↵
- The remaining rows only **shift values downward**↵
↵
---↵
↵
### Time Complexity↵
↵
$$↵
\begin{align}↵
\text{Matrix multiplication} &= O(k^3) \\↵
\text{Binary exponentiation} &= O(\log n) \\↵
\Rightarrow \text{Total} &= O(k^3 \log n)↵
\end{align}↵
$$↵
↵
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:↵
$$↵
\begin{align}↵
dp[1] &\leftrightarrow x \cdot dp[0] \\↵
dp[2] &\leftrightarrow x^2 \cdot dp[0] \\↵
dp[n] &\leftrightarrow x^n \cdot dp[0]↵
\end{align}↵
$$↵
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:↵
$$↵
\begin{align}↵
dp[k] &= c_1 dp[k-1] + c_2 dp[k-2] + \dots + c_k dp[0]↵
\end{align}↵
$$↵
Replace \( dp[i] \) with powers of \( x \):↵
$$↵
\begin{align}↵
x^k &\equiv c_1 x^{k-1} + c_2 x^{k-2} + \dots + c_k↵
\end{align}↵
$$↵
Move everything to the left-hand side:↵
$$↵
\begin{align}↵
x^k - c_1 x^{k-1} - c_2 x^{k-2} - \dots - c_k &= 0↵
\end{align}↵
$$↵
Define the **characteristic polynomial**:↵
$$↵
\begin{align}↵
p(x) &= x^k - c_1 x^{k-1} - c_2 x^{k-2} - \dots - c_k↵
\end{align}↵
$$↵
↵
This polynomial encodes the recurrence completely.↵
↵
---↵
↵
### Main Idea of Kitamasa Method↵
↵
We want to compute \( x^n \).↵
↵
Using polynomial division:↵
↵
$$↵
\begin{align}↵
x^n &= Q(x)\,p(x) + R(x)↵
\end{align}↵
$$↵
↵
Taking modulo \( p(x) \):↵
↵
$$↵
\begin{align}↵
x^n &\equiv R(x) \pmod{p(x)}↵
\end{align}↵
$$↵
↵
Where:↵
↵
$$↵
\begin{align}↵
\deg R(x) &< k↵
\end{align}↵
$$↵
↵
So the remainder can be written as:↵
↵
$$↵
\begin{align}↵
R(x) &= r_0 + r_1 x + \dots + r_{k-1} x^{k-1}↵
\end{align}↵
$$↵
↵
Mapping this back to DP:↵
↵
$$↵
\begin{align}↵
dp[n] &= \sum_{i=0}^{k-1} r_i \cdot dp[i]↵
\end{align}↵
$$↵
↵
**Conclusion:** ↵
Computing \( dp[n] \) is equivalent to computing ↵
\( x^n \bmod p(x) \).↵
↵
---↵
↵
### Fibonacci Example↵
↵
Consider Fibonacci numbers:↵
↵
$$↵
\begin{align}↵
f(n) &= f(n-1) + f(n-2)↵
\end{align}↵
$$↵
↵
Here \( k = 2 \), and the characteristic polynomial is:↵
↵
$$↵
\begin{align}↵
p(x) &= x^2 - x - 1↵
\end{align}↵
$$↵
↵
Which implies:↵
↵
$$↵
\begin{align}↵
x^2 &\equiv x + 1↵
\end{align}↵
$$↵
↵
Computing **f(3)**:↵
↵
$$↵
\begin{align}↵
x^3 &= x^2 \cdot x = x(x+1) = x^2 + x = (x+1) + x = 2x + 1↵
\end{align}↵
$$↵
↵
Therefore:↵
↵
$$↵
\begin{align}↵
f(3) &= 2f(1) + f(0)↵
\end{align}↵
$$↵
↵
Computing **f(4)**:↵
↵
$$↵
\begin{align}↵
x^4 &= x^2 \cdot x^2 = (x+1)(x+1) = x^2 + 2x + 1 = (x+1) + 2x + 1 &= 3x + 2↵
\end{align}↵
$$↵
↵
Thus:↵
↵
$$↵
\begin{align}↵
f(4) &= 3f(1) + 2f(0)↵
\end{align}↵
$$↵
↵
---↵
## Binary Exponentiation on Polynomials↵
↵
Assume we already know:↵
↵
$$↵
\begin{align}↵
x^n &\equiv R(x) \pmod{p(x)}↵
\end{align}↵
$$↵
↵
To compute **(x^(2n))**:↵
↵
$$↵
\begin{align}↵
x^{2n} &= (x^n)^2 = R(x)^2 \pmod{p(x)}↵
\end{align}↵
$$↵
↵
Steps:↵
1. Multiply two polynomials of degree \( < k \)↵
2. Reduce the result modulo p(x).↵
↵
Each step costs **O(k^2)**.↵
↵
---↵
↵
## Final Complexity↵
↵
$$↵
\begin{align}↵
\text{Polynomial multiplication} &= O(k^2) \\↵
\text{Exponentiation steps} &= O(\log n) \\↵
\Rightarrow \text{Total} &= O(k^2 \log n)↵
\end{align}↵
$$↵
↵
Using FFT:↵
↵
$$↵
\begin{align}↵
\text{Total} &= O(k \log k \log n)↵
\end{align}↵
$$↵
↵
↵
--- ↵
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 \):↵
↵
$$↵
\begin{align}↵
dp[n] &= c_1 \cdot dp[n-1] + c_2 \cdot dp[n-2] + \dots + c_k \cdot dp[n-k]↵
\end{align}↵
$$↵
↵
Along with the first \( k \) values:↵
↵
$$↵
\begin{align}↵
dp[0],\ dp[1],\ \dots,\ dp[k-1]↵
\end{align}↵
$$↵
↵
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:↵
↵
$$↵
\begin{align}↵
V(i) &= [\, dp[i],\ dp[i-1],\ dp[i-2],\ \dots,\ dp[i-k+1] \,]↵
\end{align}↵
$$↵
↵
This vector fully describes the DP state at step \( i \).↵
↵
↵
**Transition Rule**↵
There exists a fixed matrix \( M \) such that:↵
↵
$$↵
\begin{align}↵
V(i+1) &= M \cdot V(i)↵
\end{align}↵
$$↵
↵
Applying this transition repeatedly:↵
↵
$$↵
\begin{align}↵
V(n) &= M^{\,n-k} \cdot V(k)↵
\end{align}↵
$$↵
↵
So the problem reduces to exponentiating a matrix.↵
↵
↵
**Transition Matrix**↵
The transition matrix has the following form:↵
↵
$$↵
\begin{align}↵
M &=↵
\begin{bmatrix}↵
c_1 & c_2 & \dots & c_k \\↵
1 & 0 & \dots & 0 \\↵
0 & 1 & \dots & 0 \\↵
\vdots & \vdots & \ddots & \vdots \\↵
0
\end{bmatrix}↵
\end{align}↵
$$↵
↵
- The **first row** applies the recurrence↵
- The remaining rows only **shift values downward**↵
↵
---↵
↵
### Time Complexity↵
↵
$$↵
\begin{align}↵
\text{Matrix multiplication} &= O(k^3) \\↵
\text{Binary exponentiation} &= O(\log n) \\↵
\Rightarrow \text{Total} &= O(k^3 \log n)↵
\end{align}↵
$$↵
↵
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:↵
$$↵
\begin{align}↵
dp[1] &\leftrightarrow x \cdot dp[0] \\↵
dp[2] &\leftrightarrow x^2 \cdot dp[0] \\↵
dp[n] &\leftrightarrow x^n \cdot dp[0]↵
\end{align}↵
$$↵
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:↵
$$↵
\begin{align}↵
dp[k] &= c_1 dp[k-1] + c_2 dp[k-2] + \dots + c_k dp[0]↵
\end{align}↵
$$↵
Replace \( dp[i] \) with powers of \( x \):↵
$$↵
\begin{align}↵
x^k &\equiv c_1 x^{k-1} + c_2 x^{k-2} + \dots + c_k↵
\end{align}↵
$$↵
Move everything to the left-hand side:↵
$$↵
\begin{align}↵
x^k - c_1 x^{k-1} - c_2 x^{k-2} - \dots - c_k &= 0↵
\end{align}↵
$$↵
Define the **characteristic polynomial**:↵
$$↵
\begin{align}↵
p(x) &= x^k - c_1 x^{k-1} - c_2 x^{k-2} - \dots - c_k↵
\end{align}↵
$$↵
↵
This polynomial encodes the recurrence completely.↵
↵
---↵
↵
### Main Idea of Kitamasa Method↵
↵
We want to compute \( x^n \).↵
↵
Using polynomial division:↵
↵
$$↵
\begin{align}↵
x^n &= Q(x)\,p(x) + R(x)↵
\end{align}↵
$$↵
↵
Taking modulo \( p(x) \):↵
↵
$$↵
\begin{align}↵
x^n &\equiv R(x) \pmod{p(x)}↵
\end{align}↵
$$↵
↵
Where:↵
↵
$$↵
\begin{align}↵
\deg R(x) &< k↵
\end{align}↵
$$↵
↵
So the remainder can be written as:↵
↵
$$↵
\begin{align}↵
R(x) &= r_0 + r_1 x + \dots + r_{k-1} x^{k-1}↵
\end{align}↵
$$↵
↵
Mapping this back to DP:↵
↵
$$↵
\begin{align}↵
dp[n] &= \sum_{i=0}^{k-1} r_i \cdot dp[i]↵
\end{align}↵
$$↵
↵
**Conclusion:** ↵
Computing \( dp[n] \) is equivalent to computing ↵
\( x^n \bmod p(x) \).↵
↵
---↵
↵
### Fibonacci Example↵
↵
Consider Fibonacci numbers:↵
↵
$$↵
\begin{align}↵
f(n) &= f(n-1) + f(n-2)↵
\end{align}↵
$$↵
↵
Here \( k = 2 \), and the characteristic polynomial is:↵
↵
$$↵
\begin{align}↵
p(x) &= x^2 - x - 1↵
\end{align}↵
$$↵
↵
Which implies:↵
↵
$$↵
\begin{align}↵
x^2 &\equiv x + 1↵
\end{align}↵
$$↵
↵
Computing **f(3)**:↵
↵
$$↵
\begin{align}↵
x^3 &= x^2 \cdot x = x(x+1) = x^2 + x = (x+1) + x = 2x + 1↵
\end{align}↵
$$↵
↵
Therefore:↵
↵
$$↵
\begin{align}↵
f(3) &= 2f(1) + f(0)↵
\end{align}↵
$$↵
↵
Computing **f(4)**:↵
↵
$$↵
\begin{align}↵
x^4 &= x^2 \cdot x^2 = (x+1)(x+1) = x^2 + 2x + 1 = (x+1) + 2x + 1 &= 3x + 2↵
\end{align}↵
$$↵
↵
Thus:↵
↵
$$↵
\begin{align}↵
f(4) &= 3f(1) + 2f(0)↵
\end{align}↵
$$↵
↵
---↵
## Binary Exponentiation on Polynomials↵
↵
Assume we already know:↵
↵
$$↵
\begin{align}↵
x^n &\equiv R(x) \pmod{p(x)}↵
\end{align}↵
$$↵
↵
To compute **(x^(2n))**:↵
↵
$$↵
\begin{align}↵
x^{2n} &= (x^n)^2 = R(x)^2 \pmod{p(x)}↵
\end{align}↵
$$↵
↵
Steps:↵
1. Multiply two polynomials of degree \( < k \)↵
2. Reduce the result modulo p(x).↵
↵
Each step costs **O(k^2)**.↵
↵
---↵
↵
## Final Complexity↵
↵
$$↵
\begin{align}↵
\text{Polynomial multiplication} &= O(k^2) \\↵
\text{Exponentiation steps} &= O(\log n) \\↵
\Rightarrow \text{Total} &= O(k^2 \log n)↵
\end{align}↵
$$↵
↵
Using FFT:↵
↵
$$↵
\begin{align}↵
\text{Total} &= O(k \log k \log n)↵
\end{align}↵
$$↵
↵
↵
