test/math/matrix/aoj_3079.test.cpp

• View this file on GitHub
• Last update: 2024-10-12 16:54:24+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/3079

Depends on

• 行列 (src/math/matrix.hpp)
• Mod Int (src/math/mod_int.hpp)

Code

// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/3079

#include "src/math/matrix.hpp"
#include "src/math/mod_int.hpp"

#include <iostream>

using namespace std;

int main() {
	long long n;
	cin >> n;
	Matrix<ModInt<int>> a(3), b(3, 1);
	a[0][1] = a[0][2] = a[1][0] = a[2][1] = 1;
	b[0][0] = 1;
	cout << (a.pow(n) * b)[0][0] << endl;

	return 0;
}

#line 1 "test/math/matrix/aoj_3079.test.cpp"
// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/3079

#line 1 "src/math/matrix.hpp"



#include <cassert>
#include <cstddef>
#include <initializer_list>
#include <vector>

template<class T>
class Matrix {
private:
	std::vector<std::vector<T>> mat;

public:
	Matrix(std::size_t n) : mat(n, std::vector<T>(n)) {}

	Matrix(std::size_t n, std::size_t m) : mat(n, std::vector<T>(m)) {}

	Matrix(std::initializer_list<std::vector<T>> init) : mat(init) {}

	Matrix(std::vector<std::vector<T>> &mat) : mat(mat) {}

	[[nodiscard]] std::size_t height() const { return mat.size(); }

	[[nodiscard]] std::size_t width() const { return mat[0].size(); }

	std::vector<T> &operator[](std::size_t k) { return mat[k]; }

	std::vector<T> const &operator[](std::size_t k) const { return mat[k]; }

	Matrix &operator+=(Matrix const &b) {
		std::size_t n = height(), m = width();
		assert(n == b.height() && m == b.width());
		for (std::size_t i = 0; i < n; ++i)
			for (std::size_t j = 0; j < m; ++j) (*this)[i][j] += b[i][j];
		return *this;
	}

	Matrix &operator-=(Matrix const &b) {
		std::size_t n = height(), m = width();
		assert(n == b.height() && m == b.width());
		for (std::size_t i = 0; i < n; ++i)
			for (std::size_t j = 0; j < m; ++j) (*this)[i][j] -= b[i][j];
		return *this;
	}

	Matrix &operator*=(Matrix const &b) {
		std::size_t n = height(), m = b.width(), p = width();
		assert(p == b.height());
		std::vector<std::vector<T>> c(n, std::vector<T>(m));
		for (std::size_t i = 0; i < n; ++i)
			for (std::size_t j = 0; j < m; ++j)
				for (std::size_t k = 0; k < p; ++k) c[i][j] += (*this)[i][k] * b[k][j];
		mat.swap(c);
		return *this;
	}

	Matrix operator+(Matrix const &b) const { return Matrix(*this) += b; }

	Matrix operator-(Matrix const &b) const { return Matrix(*this) -= b; }

	Matrix operator*(Matrix const &b) const { return Matrix(*this) *= b; }

	static Matrix identity(std::size_t n) {
		Matrix id(n);
		for (std::size_t i = 0; i < n; ++i) id[i][i] = 1;
		return id;
	}

	[[nodiscard]] Matrix pow(long long n) const {
		Matrix res = Matrix::identity(height()), tmp(*this);
		while (n > 0) {
			if (n & 1) res *= tmp;
			tmp *= tmp;
			n >>= 1;
		}
		return res;
	}
};


#line 1 "src/math/mod_int.hpp"



#include <iostream>

template<class T, T MOD = 1000000007>
class ModInt {
private:
	T x;

public:
	ModInt() : x(0) {}

	ModInt(T y) : x(y % MOD) {
		if (x < 0) x += MOD;
	}

	ModInt &operator+=(ModInt const &a) {
		x += a.x;
		if (x >= MOD) x -= MOD;
		return *this;
	}

	ModInt &operator-=(ModInt const &a) {
		x += MOD - a.x;
		if (x >= MOD) x -= MOD;
		return *this;
	}

	ModInt &operator*=(ModInt const &a) {
		x = 1LL * x * a.x % MOD;
		return *this;
	}

	ModInt &operator/=(ModInt const &a) {
		*this *= a.inv();
		return *this;
	}

	ModInt operator+(ModInt const &a) const { return ModInt(x) += a; }

	ModInt operator-(ModInt const &a) const { return ModInt(x) -= a; }

	ModInt operator*(ModInt const &a) const { return ModInt(x) *= a; }

	ModInt operator/(ModInt const &a) const { return ModInt(x) /= a; }

	ModInt operator-() const { return ModInt(-x); }

	bool operator==(ModInt const &a) const { return x == a.x; }

	bool operator!=(ModInt const &a) const { return x != a.x; }

	bool operator<(ModInt const &a) const { return x < a.x; }

	friend std::ostream &operator<<(std::ostream &os, ModInt const &a) {
		return os << a.x;
	}

	friend std::istream &operator>>(std::istream &is, ModInt &a) {
		T t;
		is >> t;
		a = ModInt(t);
		return is;
	}

	[[nodiscard]] ModInt inv() const {
		T a = x, b = MOD, u = 1, v = 0;
		while (b > 0) {
			T t = a / b;
			a -= t * b, u -= t * v;
			std::swap(a, b);
			std::swap(u, v);
		}
		return ModInt(u);
	}

	[[nodiscard]] ModInt pow(long long n) const {
		ModInt res(1), tmp(x);
		while (n > 0) {
			if (n & 1) res *= tmp;
			tmp *= tmp;
			n >>= 1;
		}
		return res;
	}

	static ModInt comb(long long n, long long k) {
		ModInt num(1), den(1);
		for (int i = 0; i < k; ++i) {
			num *= ModInt(n - i);
			den *= ModInt(i + 1);
		}
		return num / den;
	}
};


#line 5 "test/math/matrix/aoj_3079.test.cpp"

#line 7 "test/math/matrix/aoj_3079.test.cpp"

using namespace std;

int main() {
	long long n;
	cin >> n;
	Matrix<ModInt<int>> a(3), b(3, 1);
	a[0][1] = a[0][2] = a[1][0] = a[2][1] = 1;
	b[0][0] = 1;
	cout << (a.pow(n) * b)[0][0] << endl;

	return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_01.in	AC	13 ms	7 MB
g++	00_sample_02.in	AC	12 ms	7 MB
g++	00_sample_03.in	AC	12 ms	7 MB
g++	10_small_01.in	AC	12 ms	7 MB
g++	10_small_02.in	AC	12 ms	7 MB
g++	10_small_03.in	AC	12 ms	7 MB
g++	10_small_04.in	AC	12 ms	7 MB
g++	10_small_05.in	AC	12 ms	7 MB
g++	10_small_06.in	AC	12 ms	7 MB
g++	10_small_07.in	AC	12 ms	7 MB
g++	10_small_08.in	AC	12 ms	7 MB
g++	10_small_09.in	AC	12 ms	7 MB
g++	10_small_10.in	AC	12 ms	7 MB
g++	10_small_11.in	AC	12 ms	7 MB
g++	10_small_12.in	AC	12 ms	7 MB
g++	10_small_13.in	AC	12 ms	7 MB
g++	10_small_14.in	AC	12 ms	7 MB
g++	10_small_15.in	AC	13 ms	7 MB
g++	10_small_16.in	AC	12 ms	7 MB
g++	10_small_17.in	AC	12 ms	7 MB
g++	10_small_18.in	AC	12 ms	7 MB
g++	10_small_19.in	AC	12 ms	7 MB
g++	10_small_20.in	AC	12 ms	7 MB
g++	20_random_01.in	AC	12 ms	7 MB
g++	20_random_02.in	AC	12 ms	7 MB
g++	20_random_03.in	AC	12 ms	7 MB
g++	20_random_04.in	AC	12 ms	7 MB
g++	20_random_05.in	AC	12 ms	7 MB
g++	20_random_06.in	AC	12 ms	7 MB
g++	20_random_07.in	AC	13 ms	7 MB
g++	20_random_08.in	AC	12 ms	7 MB
g++	20_random_09.in	AC	12 ms	7 MB
g++	20_random_10.in	AC	13 ms	7 MB
g++	30_large_01.in	AC	12 ms	7 MB
g++	30_large_02.in	AC	12 ms	7 MB
g++	30_large_03.in	AC	12 ms	7 MB
g++	30_large_04.in	AC	12 ms	7 MB
g++	30_large_05.in	AC	12 ms	7 MB
g++	30_large_06.in	AC	12 ms	7 MB
g++	30_large_07.in	AC	12 ms	7 MB
g++	30_large_08.in	AC	13 ms	7 MB
g++	30_large_09.in	AC	13 ms	7 MB
g++	30_large_10.in	AC	13 ms	7 MB
g++	30_large_11.in	AC	12 ms	7 MB
g++	30_large_12.in	AC	12 ms	7 MB
g++	30_large_13.in	AC	12 ms	7 MB
g++	30_large_14.in	AC	12 ms	7 MB
g++	30_large_15.in	AC	13 ms	7 MB
g++	30_large_16.in	AC	12 ms	7 MB
g++	30_large_17.in	AC	13 ms	7 MB
g++	30_large_18.in	AC	13 ms	7 MB
g++	30_large_19.in	AC	12 ms	7 MB
g++	30_large_20.in	AC	12 ms	7 MB
clang++	00_sample_01.in	AC	11 ms	9 MB
clang++	00_sample_02.in	AC	12 ms	15 MB
clang++	00_sample_03.in	AC	12 ms	9 MB
clang++	10_small_01.in	AC	11 ms	11 MB
clang++	10_small_02.in	AC	11 ms	9 MB
clang++	10_small_03.in	AC	11 ms	13 MB
clang++	10_small_04.in	AC	11 ms	7 MB
clang++	10_small_05.in	AC	11 ms	7 MB
clang++	10_small_06.in	AC	11 ms	13 MB
clang++	10_small_07.in	AC	12 ms	9 MB
clang++	10_small_08.in	AC	11 ms	7 MB
clang++	10_small_09.in	AC	11 ms	7 MB
clang++	10_small_10.in	AC	11 ms	9 MB
clang++	10_small_11.in	AC	11 ms	11 MB
clang++	10_small_12.in	AC	12 ms	13 MB
clang++	10_small_13.in	AC	11 ms	11 MB
clang++	10_small_14.in	AC	12 ms	15 MB
clang++	10_small_15.in	AC	11 ms	9 MB
clang++	10_small_16.in	AC	11 ms	11 MB
clang++	10_small_17.in	AC	11 ms	9 MB
clang++	10_small_18.in	AC	12 ms	11 MB
clang++	10_small_19.in	AC	12 ms	11 MB
clang++	10_small_20.in	AC	11 ms	9 MB
clang++	20_random_01.in	AC	11 ms	13 MB
clang++	20_random_02.in	AC	11 ms	11 MB
clang++	20_random_03.in	AC	12 ms	13 MB
clang++	20_random_04.in	AC	12 ms	11 MB
clang++	20_random_05.in	AC	12 ms	9 MB
clang++	20_random_06.in	AC	12 ms	11 MB
clang++	20_random_07.in	AC	11 ms	7 MB
clang++	20_random_08.in	AC	11 ms	9 MB
clang++	20_random_09.in	AC	11 ms	11 MB
clang++	20_random_10.in	AC	11 ms	9 MB
clang++	30_large_01.in	AC	11 ms	13 MB
clang++	30_large_02.in	AC	12 ms	9 MB
clang++	30_large_03.in	AC	12 ms	9 MB
clang++	30_large_04.in	AC	11 ms	9 MB
clang++	30_large_05.in	AC	11 ms	11 MB
clang++	30_large_06.in	AC	11 ms	11 MB
clang++	30_large_07.in	AC	11 ms	15 MB
clang++	30_large_08.in	AC	12 ms	13 MB
clang++	30_large_09.in	AC	11 ms	11 MB
clang++	30_large_10.in	AC	11 ms	7 MB
clang++	30_large_11.in	AC	11 ms	11 MB
clang++	30_large_12.in	AC	12 ms	11 MB
clang++	30_large_13.in	AC	12 ms	13 MB
clang++	30_large_14.in	AC	13 ms	13 MB
clang++	30_large_15.in	AC	12 ms	15 MB
clang++	30_large_16.in	AC	11 ms	7 MB
clang++	30_large_17.in	AC	11 ms	9 MB
clang++	30_large_18.in	AC	12 ms	13 MB
clang++	30_large_19.in	AC	12 ms	9 MB
clang++	30_large_20.in	AC	12 ms	15 MB

Back to top page