math/Fibonacci.cpp

• View this file on GitHub
• Last update: 2021-04-29 10:14:35+09:00

Depends on

• math/Matrix.cpp

Verified with

• test/EnumerateFibonacci.test.cpp
• test/Fibonacci.test.cpp

Code

#pragma once
#include "./Matrix.cpp"
#include <vector>

template <class value_type> value_type Fibonacci(long long n) {
	Matrix<value_type> A(std::vector<std::vector<value_type>>{{1, 1}, {1, 0}});
	Matrix<value_type> B(std::vector<std::vector<value_type>>{{1}, {0}});
	return (A.pow(n) * B)[1][0];
}

template <class value_type = long long> std::vector<value_type> EnumerateFibonacci(int n) {
	std::vector<value_type> result(n + 1);
	for (int i = 0; i <= n; ++i) {
		if (i < 2) {
			result[i] = i;
		} else {
			result[i] = result[i - 1] + result[i - 2];
		}
	}
	return result;
}

#line 2 "math/Matrix.cpp"
#include <vector>
#include <cassert>
#include <initializer_list>

template <class T> struct Matrix {
public:
	using value_type = T;
	using data_type = std::vector<std::vector<value_type>>;

private:
	std::size_t h, w;
	data_type A;

public:
	static Matrix I(std::size_t n) {
		Matrix A(n);
		for (std::size_t i = 0; i < n; ++i) {
			A[i][i] = 1;
		}
		return A;
	}
	Matrix() {}
	Matrix(std::size_t _h, std::size_t _w) : h(_h), w(_w), A(h, std::vector<T>(w, 0)) {}
	Matrix(std::size_t _h) : h(_h), w(_h), A(h, std::vector<T>(w, 0)) {}
	Matrix(const data_type& _A) : h(_A.size()), w(_A[0].size()), A(_A) {}
	Matrix(std::initializer_list<std::vector<value_type>> init)
	    : h(init.size()), w(init.begin()->size()), A(init) {}
	std::size_t height() const {
		return h;
	}
	std::size_t width() const {
		return w;
	}
	const data_type& value() const {
		return A;
	}
	const std::vector<T>& operator[](int i) const {
		return A[i];
	}
	std::vector<T>& operator[](int i) {
		return A[i];
	}
	const data_type& operator*() const {
		return A;
	}
	Matrix& operator+=(const Matrix& B) {
		assert(h == B.height() && w == B.width());
		for (std::size_t i = 0; i < h; ++i) {
			for (std::size_t j = 0; j < w; ++j) {
				A[i][j] += B[i][j];
			}
		}
		return *this;
	}
	Matrix& operator-=(const Matrix& B) {
		assert(h == B.height() && w == B.width());
		for (std::size_t i = 0; i < h; ++i) {
			for (std::size_t j = 0; j < w; ++j) {
				A[i][j] -= B[i][j];
			}
		}
		return *this;
	}
	Matrix& operator*=(const Matrix& B) {
		std::size_t n = B.width();
		assert(w == B.height());
		data_type C(h, std::vector<T>(n, 0));
		for (std::size_t i = 0; i < h; i++) {
			for (std::size_t j = 0; j < n; j++) {
				for (std::size_t k = 0; k < w; k++) {
					C[i][j] += A[i][k] * B[k][j];
				}
			}
		}
		A.swap(C);
		return *this;
	}
	Matrix& operator^=(long long k) {
		Matrix B = Matrix::I(h);
		while (k > 0) {
			if (k & 1) {
				B *= *this;
			}
			*this *= *this;
			k >>= 1;
		}
		A.swap(B.A);
		return *this;
	}
	Matrix operator+(const Matrix& B) const {
		return Matrix(*this) += B;
	}
	Matrix operator-(const Matrix& B) const {
		return Matrix(*this) -= B;
	}
	Matrix operator*(const Matrix& B) const {
		return Matrix(*this) *= B;
	}
	Matrix operator^(const long long k) const {
		return Matrix(*this) ^= k;
	}
	Matrix pow(long long k) const {
		return *this ^ k;
	}
};
#line 4 "math/Fibonacci.cpp"

template <class value_type> value_type Fibonacci(long long n) {
	Matrix<value_type> A(std::vector<std::vector<value_type>>{{1, 1}, {1, 0}});
	Matrix<value_type> B(std::vector<std::vector<value_type>>{{1}, {0}});
	return (A.pow(n) * B)[1][0];
}

template <class value_type = long long> std::vector<value_type> EnumerateFibonacci(int n) {
	std::vector<value_type> result(n + 1);
	for (int i = 0; i <= n; ++i) {
		if (i < 2) {
			result[i] = i;
		} else {
			result[i] = result[i - 1] + result[i - 2];
		}
	}
	return result;
}

Back to top page