結果

問題 No.891 隣接3項間の漸化式
ユーザー MarcusAureliusAntoninusMarcusAureliusAntoninus
提出日時 2019-09-20 22:24:40
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 5,540 bytes
コンパイル時間 2,016 ms
コンパイル使用メモリ 204,404 KB
最終ジャッジ日時 2025-01-07 18:45:33
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 39
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:244:19: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 2 has type ‘int64_t*’ {aka ‘long int*’} [-Wformat=]
  244 |         scanf("%lld%lld%lld", &a, &b, &n);
      |                ~~~^           ~~
      |                   |           |
      |                   |           int64_t* {aka long int*}
      |                   long long int*
      |                %ld
main.cpp:244:23: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 3 has type ‘int64_t*’ {aka ‘long int*’} [-Wformat=]
  244 |         scanf("%lld%lld%lld", &a, &b, &n);
      |                    ~~~^           ~~
      |                       |           |
      |                       |           int64_t* {aka long int*}
      |                       long long int*
      |                    %ld
main.cpp:244:27: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 4 has type ‘int64_t*’ {aka ‘long int*’} [-Wformat=]
  244 |         scanf("%lld%lld%lld", &a, &b, &n);
      |                        ~~~^           ~~
      |                           |           |
      |                           |           int64_t* {aka long int*}
      |                           long long int*
      |                        %ld
main.cpp:244:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  244 |         scanf("%lld%lld%lld", &a, &b, &n);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff #

#include <bits/stdc++.h>

////////////
// ModInt //
////////////

// 四則演算の最も左に存在する値がModIntでなければキャストでバグる
// 例えばx = mint * 1000;やx = ModInt(1000) * mint;はいいがx = 1000 * mint;は駄目。
template<int64_t mod_ = 1'000'000'007>
class ModInt {
private:
	int64_t integer_;

public:
	constexpr ModInt(const int64_t initial_number = 0)
		: integer_(initial_number){}
	
	// 四則演算
	constexpr ModInt operator+(const ModInt& operand) const
	{
		ModInt ret{this->integer_ + operand.integer_};
		if (ret.integer_ >= mod_)
			ret.integer_ -= mod_;
		return ret;
	}
	constexpr ModInt operator-(const ModInt& operand) const
	{
		ModInt ret{this->integer_ - operand.integer_};
		if (ret.integer_ < 0)
			ret.integer_ += mod_;
		return ret;
	}
	constexpr ModInt operator*(const ModInt& operand) const
	{
		return {this->integer_ * operand.integer_ % mod_};
	}
	constexpr ModInt operator/(const ModInt& operand) const
	{
		return *this * (operand ^ (mod_ - 2));
	}

	// 単項演算子
	constexpr ModInt& operator++()
	{
		if (integer_ + 1 == mod_) integer_ = 0;
		else integer_++;
		return *this;
	}

	constexpr ModInt& operator--()
	{
		if (integer_ == 0) integer_ = mod_ - 1;
		else integer_--;
		return *this;
	}

	constexpr ModInt operator+()
	{
		return *this;
	}

	constexpr ModInt operator-()
	{
		if (integer_ == 0) return ModInt(0ll);
		else return ModInt(mod_ - integer_);
	}

	// 累乗
	constexpr ModInt operator^(const int64_t operand) const
	{
		ModInt ret{1}, pow_ope{this->integer_};
		for (int64_t pow{operand}; pow > 0; pow >>= 1)
		{
			if (pow & 1) ret *= pow_ope;
			pow_ope *= pow_ope;
		}
		return ret;
	}

	// 代入
	constexpr ModInt& operator=(const ModInt& operand)
	{
		this->integer_ = operand.integer_;
		return *this;
	}
	constexpr ModInt& operator+=(const ModInt& operand)
	{
		*this = *this + operand;
		return *this;
	}
	constexpr ModInt& operator-=(const ModInt& operand)
	{
		*this = *this - operand;
		return *this;
	}
	constexpr ModInt& operator*=(const ModInt& operand)
	{
		*this = *this * operand;
		return *this;
	}
	constexpr ModInt& operator/=(const ModInt& operand)
	{
		*this = *this / operand;
		return *this;
	}

	// その他
	constexpr operator int64_t() { return integer_; }

	constexpr ModInt getOne() const
	{
		return ModInt(1ll);
	}
	constexpr ModInt getZero() const
	{
		return ModInt(0ll);
	}
};
using Mint = ModInt<>;

////////////
// 行列型 //
///////////

// 加算、減算、乗算をもつM×N型行列
// M=Nで環をつくる
template<typename T = int64_t>
class Matrix {
private:
	using RowVector = std::vector<T>;

	std::vector<RowVector> container_;

	// 必要に応じて書換
	const T ring_one{1ll};
	const T ring_zero{};

public:
	const int M, N;

	Matrix(const int row_size, const int column_size)
		: M(row_size), N(column_size), container_(row_size, RowVector(column_size)){}
	// ムーブコンストラクタ
	Matrix(Matrix&& mat)
		: M(mat.M), N(mat.N), container_(std::move(mat.container_)){}
	// コピーコンストラクタ
	Matrix(const Matrix& mat)
		: M(mat.M), N(mat.N), container_(mat.container_){}

	// 要素アクセス
	RowVector& operator[](const int r) { return container_[r]; }
	const RowVector& operator[](const int r) const { return container_[r]; }
	// イテレータ
	typename decltype(container_)::iterator begin(){ return container_.begin(); }
	typename decltype(container_)::iterator end(){ return container_.end(); }

	// 環の演算
	Matrix operator+(const Matrix& mat) const
	{
		Matrix ret{*this};
		for (int r_i{}; r_i < M; r_i++)
			for (int c_i{}; c_i < N; c_i++)
				ret[r_i][c_i] += mat[r_i][c_i];
		return std::move(ret);
	}
	Matrix operator-(const Matrix& mat) const
	{
		Matrix ret{*this};
		for (int r_i{}; r_i < M; r_i++)
			for (int c_i{}; c_i < N; c_i++)
				ret[r_i][c_i] -= mat[r_i][c_i];
		return std::move(ret);
	}
	Matrix operator*(const Matrix& mat) const
	{
		Matrix ret(this->M, mat.N);
		for (int r_i{}; r_i < this->M; r_i++)
			for (int c_i{}; c_i < mat.N; c_i++)
				for (int l_i{}; l_i < this->N; l_i++)
					ret[r_i][c_i] += (*this)[r_i][l_i] * mat[l_i][c_i];
		return std::move(ret);
	}
	std::vector<T> operator*(const std::vector<T>& vec) const
	{
		std::vector<T> ret(M);
		for (int r_i{}; r_i < M; r_i++)
			for (int c_i{}; c_i < N; c_i++)
				ret[r_i] += (*this)[r_i][c_i] * vec[c_i];
		return std::move(ret);
	}

	// 累乗
	Matrix operator^(const int64_t index) const
	{
		Matrix ret((*this).getOne()), pow(*this);
		for (int64_t i{index}; i > 0; i >>= 1)
		{
			if (i & 1)
				ret *= pow;
			pow *= pow;
		}
		return std::move(ret);
	}

	// 代入演算子
	Matrix& operator=(const Matrix& mat)
	{
		this->container_ = mat.container_;
		return *this;
	}	
	Matrix& operator+=(const Matrix& mat)
	{
		*this = *this + mat;
		return *this;
	}
	Matrix& operator-=(const Matrix& mat)
	{
		*this = *this - mat;
		return *this;
	}
	Matrix& operator*=(const Matrix& mat)
	{
		*this = *this * mat;
		return *this;
	}

	// ゼロ行列と単位行列
	constexpr Matrix getOne() const
	{
		Matrix ret(M, N);
		for (int i{}; i < N; i++)
			ret[i][i] = ring_one;
		return std::move(ret);
	}
	constexpr Matrix getZero() const
	{
		return Matrix(M, N);
	}
};

int main()
{
	int64_t a, b, n;
	scanf("%lld%lld%lld", &a, &b, &n);
	using Mat = Matrix<Mint>;
	Mat mat(2, 2);
	mat[0][0] = Mint(0ll); mat[0][1] = Mint(1ll);
	mat[1][0] = Mint(b); mat[1][1] = Mint(a);
	std::vector<Mint> vec{0, 1};
	std::cout << ((mat ^ n) * vec)[0] << std::endl;

	return 0;
}
0