This is the first activity of Computerization algorithm team. We introduced the method to find the th term of the Fibonacci sequence, which mainly uses matrix exponentiation.
Problem
Given , find 。
Input constraints | Memory limit | Execution time |
---|---|---|
64MB | 1.0s |
Solution
The input size of obviously prohibits any attempt to solve it with loops. Is there a better way than a simple ? It turns out that with matrix exponentiation, we can achieve . We observe that:
This step is applicable to all recursive sequences, so it should be easily reached for an experienced candidate. Generally, for , we have
From the recursive definition,
Substituting ,
Now the problem is transformed into finding the matrix raised to the th power. If (representation in binary), then
The th powers of the original matrix can, in fact, be preprocessed. When , , so we only need to store at most 63 matrices. In addition,
which implies that the powers can be attained within time. This is the idea of fast matrix exponentiation: compute all th powers, and put those needed together.
Program
Below is the C++ code, where the most intractable part is probably implementation of matrix multiplication:
#include <iostream>
#include <cmath>
using namespace std;
struct mat {
unsigned long long a[4];
mat operator *(mat o) {
mat t;
t.a[0] = (this->a[0] * o.a[0] + this->a[1] * o.a[2]) % 1000000007;
t.a[1] = (this->a[0] * o.a[1] + this->a[1] * o.a[3]) % 1000000007;
t.a[2] = (this->a[2] * o.a[0] + this->a[3] * o.a[2]) % 1000000007;
t.a[3] = (this->a[2] * o.a[1] + this->a[3] * o.a[3]) % 1000000007;
return t;
}
};
// Preprocessed matrices raised to the 2^k power
mat mat_pow[64];
int fib(unsigned long long k) {
// Temporary matrix; each time multiply it by some term in mat_pow
mat tmp;
tmp.a[0] = 1;
tmp.a[1] = 0;
tmp.a[2] = 0;
tmp.a[3] = 1;
for (int i = 0; i < 64; i++) {
// If a_i is 1
if (k & (1ull << i)) {
tmp = tmp * mat_pow[i];
}
}
return tmp.a[1];
}
int main() {
mat_pow[0].a[0] = 0;
mat_pow[0].a[1] = 1;
mat_pow[0].a[2] = 1;
mat_pow[0].a[3] = 1;
for (int i = 1; i < 64; i++) {
mat_pow[i] = mat_pow[i-1] * mat_pow[i-1];
}
unsigned long long n;
cin >> n;
cout << fib(n) << endl;
return 0;
}
The formulae for matrix multiplication are: