結果

問題 No.793 うし数列 2
コンテスト
ユーザー a
提出日時 2019-02-23 05:05:40
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 4,607 bytes
コンパイル時間 1,697 ms
コンパイル使用メモリ 176,240 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-27 13:12:42
合計ジャッジ時間 2,492 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"

using namespace std;

template<class T>
struct Matrix
{
	vector<vector<T>> A;

	Matrix(size_t n) : A(n, vector<T>(n, 0)) {}
	Matrix(size_t h, size_t w) : A(h, vector<T>(w, 0)) {}
	Matrix(vector<vector<T>> &X) : A(X) {}

	inline vector<T> &operator[](int idx) {return A[idx];}
	inline const vector<T> &operator[](int idx) const {return A[idx];}

	size_t height() const {return A.size();}
	size_t width()  const {return A[0].size();}

	//ex)auto E = Matrix<int>::E(3);
	static Matrix E(int n)
	{
		Matrix e(n);
		for (int i = 0; i < n; i++) e[i][i] = 1;
		return e;
	}

	Matrix operator+(const Matrix &B) const
	{
		size_t h = this->height(), w = this->width();
		assert(h == B.height() && w == B.width());
		Matrix C(h, w);
		for (int i = 0; i < h; i++)
			for (int j = 0; j < w; j++)
			{
				C[i][j] = (*this)[i][j] + B[i][j];
			}
		return C;
	}

	Matrix operator-(const Matrix &B)
	{
		size_t h = this->height(), w = this->width();
		assert(h == B.height() && w == B.width());
		Matrix C(h, w);
		for (int i = 0; i < h; i++)
			for (int j = 0; j < w; j++)
			{
				C[i][j] = (*this)[i][j] - B[i][j];
			}
		return C;
	}

	Matrix operator*(const Matrix &B)
	{
		size_t h = this->height(), x = this->width(), w = B.width();
		assert(x == B.height());
		Matrix C(h, w);
		for (size_t i = 0; i < h; i++)
			for (size_t k = 0; k < x; k++)
				for (size_t j = 0; j < w; j++)
				{
					C[i][j] += (*this)[i][k] * B[k][j];
				}
		return C;
	}

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

	Matrix power(long k)
	{
		auto n = this->height();
		assert(k >= 0 && this->width() == n);
		auto R = Matrix<T>::E(n), C = Matrix(*this);
		while(k)
		{
			if (k&1) R *= C;
			C *= C;
			k >>= 1;
		}
		return R;
	}

	friend ostream &operator<<(ostream &o, const Matrix &A)
	{
		for (int i = 0; i < A.height(); i++)
		{
			for (int j = 0; j < A.width(); j++)
			{
				o << A[i][j] << " ";
			}
			o << endl;
		}
		return o;
	}
};

template <int p>
struct Modint
{
	int value;

	Modint() : value(0) {}
	Modint(long x) : value(x >= 0 ? x % p : (p + x % p) % p) {}

	inline Modint &operator+=(const Modint &b)
	{
		if ((this->value += b.value) >= p)
			this->value -= p;
		return (*this);
	}
	inline Modint &operator-=(const Modint &b)
	{
		if ((this->value += p - b.value) >= p)
			this->value -= p;
		return (*this);
	}
	inline Modint &operator*=(const Modint &b)
	{
		this->value = (int)((1LL * this->value * b.value) % p);
		return (*this);
	}
	inline Modint &operator/=(const Modint &b)
	{
		(*this) *= b.inverse();
		return (*this);
	}

	Modint operator+(const Modint &b) const { return Modint(*this) += b; }
	Modint operator-(const Modint &b) const { return Modint(*this) -= b; }
	Modint operator*(const Modint &b) const { return Modint(*this) *= b; }
	Modint operator/(const Modint &b) const { return Modint(*this) /= b; }

	inline Modint &operator++(int) { return (*this) += 1; }
	inline Modint &operator--(int) { return (*this) -= 1; }

	inline bool operator==(const Modint &b) const { return this->value == b.value; }
	inline bool operator!=(const Modint &b) const { return this->value != b.value; }
	inline bool operator<(const Modint &b) const { return this->value < b.value; }
	inline bool operator<=(const Modint &b) const { return this->value <= b.value; }
	inline bool operator>(const Modint &b) const { return this->value > b.value; }
	inline bool operator>=(const Modint &b) const { return this->value >= b.value; }

	//requires that "this->value and p are co-prime"
	// a_i * v + a_(i+1) * p = r_i
	// r_i = r_(i+1) * q_(i+1) * r_(i+2)
	// q == 1 (i > 1)
	// reference: https://atcoder.jp/contests/agc026/submissions/2845729 (line:93)
	inline Modint inverse() const
	{
		assert(this->value != 0);
		int r0 = p, r1 = this->value, a0 = 0, a1 = 1;
		while (r1)
		{
			int q = r0 / r1;
			r0 -= q * r1;
			swap(r0, r1);
			a0 -= q * a1;
			swap(a0, a1);
		}
		return Modint(a0);
	}

	friend istream &operator>>(istream &is, Modint<p> &a)
	{
		long t;
		is >> t;
		a = Modint<p>(t);
		return is;
	}
	friend ostream &operator<<(ostream &os, const Modint<p> &a)
	{
		return os << a.value;
	}
};

const int MOD = 1e9+7;

using Int = Modint<MOD>;

void solve()
{
	long N;
	cin >> N;
	Matrix<Int> A(2), v(2, 1);
	A[0][0] = 10;
	A[0][1] = 3;
	A[1][1] = 1;
	v[0][0] = 13;
	v[1][0] = 1;
	A = A.power(N-1);
	v = A*v;
	cout << v[0][0] << endl;
}

int main(void)
{
	solve();
	//cout << "yui(*-v・)yui" << endl;
	return 0;
}
0