結果

問題 No.147 試験監督（2）
ユーザー yuruhiyayuruhiya
提出日時 2020-10-28 19:22:08
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 5,474 bytes
コンパイル時間 5,767 ms
コンパイル使用メモリ 336,292 KB
実行使用メモリ 17,088 KB
最終ジャッジ日時 2024-07-21 22:19:19
合計ジャッジ時間 13,032 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "a.cpp"
#include <iostream>
#if __has_include(<library/dump.hpp>)
using cpp_int = long long;
#else
#include <boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
#endif
using namespace std;
#line 2 "/home/yuruhiya/programming/library/Math/Matrix.cpp"
#include <vector>
#include <cassert>
using namespace std;

template <class T> struct Matrix {
	size_t h, w;
	vector<vector<T>> A;

public:
	static Matrix I(size_t n) {
		Matrix A(n);
		for (size_t i = 0; i < n; ++i) {
			A[i][i] = 1;
		}
		return A;
	}
	Matrix() {}
	Matrix(size_t _h, size_t _w) : h(_h), w(_w), A(h, vector<T>(w, 0)) {}
	Matrix(size_t _h) : h(_h), w(_h), A(h, vector<T>(w, 0)){};
	Matrix(const vector<vector<T>>& _A) : h(_A.size()), w(_A[0].size()), A(_A) {}
	size_t height() const {
		return h;
	}
	size_t width() const {
		return w;
	}
	const vector<T>& operator[](int i) const {
		return A[i];
	}
	vector<T>& operator[](int i) {
		return A[i];
	}
	const vector<vector<T>>& operator*() const {
		return A;
	}
	Matrix& operator+=(const Matrix& B) {
		assert(h == B.height() && w == B.width());
		for (size_t i = 0; i < h; ++i) {
			for (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 (size_t i = 0; i < h; ++i) {
			for (size_t j = 0; j < w; ++j) {
				A[i][j] -= B[i][j];
			}
		}
		return *this;
	}
	Matrix& operator*=(const Matrix& B) {
		size_t n = B.width();
		assert(w == B.height());
		vector<vector<T>> C(h, vector<T>(n, 0));
		for (size_t i = 0; i < h; i++) {
			for (size_t j = 0; j < n; j++) {
				for (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 "/home/yuruhiya/programming/library/Math/Fibonacci.cpp"
using namespace std;

template <class value_type> value_type Fibonacci(long long n) {
	Matrix<value_type> A(vector<vector<value_type>>{{1, 1}, {1, 0}});
	Matrix<value_type> B(vector<vector<value_type>>{{1}, {0}});
	return (A.pow(n) * B)[1][0];
}
#line 4 "/home/yuruhiya/programming/library/Math/modint.cpp"
#include <utility>
using namespace std;

template <int MOD> struct modint {
	using T = long long;
	T n;
	constexpr modint(const T x = 0) : n(x % MOD) {
		if (n < 0) n += MOD;
	}
	constexpr int get_mod() const {
		return MOD;
	}
	constexpr modint operator+() const {
		return *this;
	}
	constexpr modint operator-() const {
		return n ? MOD - n : 0;
	}
	constexpr modint& operator++() {
		if (MOD <= ++n) n = 0;
		return *this;
	}
	constexpr modint& operator--() {
		if (n <= 0) n = MOD;
		n--;
		return *this;
	}
	constexpr modint operator++(int) {
		modint t = *this;
		++*this;
		return t;
	}
	constexpr modint operator--(int) {
		modint t = *this;
		--*this;
		return t;
	}
	constexpr modint next() const {
		return ++modint(*this);
	}
	constexpr modint pred() const {
		return --modint(*this);
	}
	constexpr modint operator+(const modint& m) const {
		return modint(*this) += m;
	}
	constexpr modint operator-(const modint& m) const {
		return modint(*this) -= m;
	}
	constexpr modint operator*(const modint& m) const {
		return modint(*this) *= m;
	}
	constexpr modint operator/(const modint& m) const {
		return modint(*this) /= m;
	}
	constexpr modint& operator+=(const modint& m) {
		n += m.n;
		if (n >= MOD) n -= MOD;
		return *this;
	}
	constexpr modint& operator-=(const modint& m) {
		n -= m.n;
		if (n < 0) n += MOD;
		return *this;
	}
	constexpr modint& operator*=(const modint& m) {
		n = n * m.n % MOD;
		return *this;
	}
	constexpr modint& operator/=(const modint& m) {
		T a = m.n, b = MOD, u = 1, v = 0;
		while (b) {
			T t = a / b;
			a -= t * b;
			swap(a, b);
			u -= t * v;
			swap(u, v);
		}
		n = n * u % MOD;
		if (n < 0) n += MOD;
		return *this;
	}
	constexpr bool operator==(const modint& m) const {
		return n == m.n;
	}
	constexpr bool operator!=(const modint& m) const {
		return n != m.n;
	}
	template <class M> constexpr modint pow(M m) const {
		if (0 <= m) {
			modint t = n, res = 1;
			while (m > 0) {
				if (m & 1) res *= t;
				t *= t;
				m >>= 1;
			}
			return res;
		} else {
			return (modint(1) / n).pow(-m);
		}
	}
	template <class M> constexpr modint operator^(M m) const {
		return pow(m);
	}
	friend ostream& operator<<(ostream& os, const modint<MOD>& m) {
		return os << m.n;
	}
	friend istream& operator>>(istream& is, modint<MOD>& m) {
		long long x;
		cin >> x;
		m = modint(x);
		return is;
	}
};
using mint = modint<1000000007>;
using VM = vector<mint>;
inline mint operator""_m(unsigned long long n) {
	return n;
}
#line 11 "a.cpp"

mint pow_mod(mint a, cpp_int b) {
	mint res = 1, k = a;
	while (b > 0) {
		if (b % 2 == 1) res *= k;
		k *= k;
		b /= 2;
	}
	return res;
}

int main() {
	mint ans = 1;
	int n;
	cin >> n;
	while (n--) {
		long long a;
		cpp_int b;
		cin >> a >> b;
		ans *= pow_mod(Fibonacci<mint>(a + 2), b);
	}
	cout << ans << endl;
}
0