Быстрое возведение матрицы в степень: как посчитать N-е число Фибоначчи за O(log n)?
Числа Фибоначчи за O(n) считать умею, но в задаче n до 10^18, и нужно F(n) mod 1e9+7. Слышал, что линейные рекурренты считаются возведением матрицы в степень за O(log n). Как это устроено и как написать matrix exponentiation на C++?
2 ответа
Линейная рекуррента превращается в умножение вектора состояния на матрицу перехода. Для Фибоначчи:
[F(n+1), F(n)] = [[1,1],[1,0]] · [F(n), F(n−1)].
Значит [[1,1],[1,0]]^n = [[F(n+1), F(n)], [F(n), F(n−1)]]. Возводим матрицу 2×2 в степень n быстрым возведением (как обычное число, только умножение — матричное):
const long long MOD = 1e9 + 7;
typedef array<array<long long,2>,2> Mat;
Mat mul(const Mat& a, const Mat& b) {
Mat c = {{{0,0},{0,0}}};
for (int i=0;i<2;i++)for(int k=0;k<2;k++)if(a[i][k])for(int j=0;j<2;j++)
c[i][j] = (c[i][j] + a[i][k]*b[k][j]) % MOD;
return c;
}
long long fib(long long n) {
if (n == 0) return 0;
Mat res = {{{1,0},{0,1}}}; // единичная
Mat base = {{{1,1},{1,0}}};
while (n) {
if (n & 1) res = mul(res, base);
base = mul(base, base);
n >>= 1;
}
return res[0][1]; // = F(n)
}
Сложность O(log n) матричных умножений; каждое умножение матрицы d×d — O(d^3), то есть для рекурренты порядка d общая сложность O(d^3 · log n). Для Фибоначчи d=2, так что фактически O(log n). Обязательно long long и % MOD после каждого сложения произведений.
Этот же приём обобщается на ЛЮБУЮ линейную рекурренту с постоянными коэффициентами a_n = c_1 a_{n−1} + ... + c_d a_{n−d}: строится «компаньон»-матрица d×d, и ответ — за O(d^3 log n). Так считают, например, число замощений, пути в графе фиксированной длины (k-я степень матрицы смежности даёт число путей длины k), линейные счётчики ДП с большим n. Для Фибоначчи есть и «удвоение» (fast doubling) — чуть быстрее матриц по константе, но матрицы универсальнее.