結果

問題 No.658 テトラナッチ数列 Hard
コンテスト
ユーザー yuruhiya
提出日時 2020-07-05 17:37:35
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 378 ms / 2,000 ms
コード長 4,585 bytes
コンパイル時間 2,371 ms
コンパイル使用メモリ 206,088 KB
最終ジャッジ日時 2025-01-11 15:59:35
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#if __has_include("/home/yuruhiya/contest/dump.hpp")
#include "/home/yuruhiya/contest/dump.hpp"
#else
#define dump(...) ((void)0)
#endif

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;
	}
	constexpr modint pow(T m) const {
		modint t = n, res = 1;
		while (m > 0) {
			if (m & 1) res *= t;
			t *= t;
			m >>= 1;
		}
		return res;
	}
	constexpr modint operator^(T 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) {
		return is >> m.n;
	}
};
using mint = modint<17>;
using VM = vector<mint>;
inline mint operator""_m(unsigned long long n) {
	return n;
}

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

public:
	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(h);
		for (size_t i = 0; i < h; ++i) {
			B[i][i] = 1;
		}
		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;
	}
};

int main() {
	int q;
	cin >> q;
	while (q--) {
		long long n;
		cin >> n;
		Matrix<mint> a({{1, 1, 1, 1}, {1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}});
		Matrix<mint> b({{1}, {0}, {0}, {0}});
		cout << (a.pow(n - 1) * b)[3][0] << endl;
	}
}
0