#676357 (C++17) No.1595 The Final Digit

提出ソース
結果

問題	No.1595 The Final Digit
ユーザー	kyon2326
提出日時	2021-07-09 22:43:28
言語	C++17 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	3 ms / 2,000 ms
コード長	16,591 bytes
コンパイル時間	5,920 ms
コンパイル使用メモリ	321,940 KB
実行使用メモリ	4,380 KB
最終ジャッジ日時	2023-09-14 10:21:23
合計ジャッジ時間	7,009 ms
ジャッジサーバーID （参考情報）	judge13 / judge15
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,376 KB
testcase_01	AC	1 ms 4,376 KB
testcase_02	AC	1 ms 4,376 KB
testcase_03	AC	1 ms 4,380 KB
testcase_04	AC	2 ms 4,380 KB
testcase_05	AC	1 ms 4,380 KB
testcase_06	AC	2 ms 4,376 KB
testcase_07	AC	2 ms 4,376 KB
testcase_08	AC	1 ms 4,380 KB
testcase_09	AC	2 ms 4,380 KB
testcase_10	AC	1 ms 4,376 KB
testcase_11	AC	2 ms 4,380 KB
testcase_12	AC	2 ms 4,376 KB
testcase_13	AC	2 ms 4,380 KB
testcase_14	AC	3 ms 4,376 KB
testcase_15	AC	2 ms 4,380 KB
testcase_16	AC	2 ms 4,380 KB
testcase_17	AC	2 ms 4,380 KB
testcase_18	AC	1 ms 4,376 KB
testcase_19	AC	1 ms 4,380 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;

#include <atcoder/all>
using namespace atcoder;

/*
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
using bll = boost::multiprecision::cpp_int;
using bdouble = boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>;
using namespace boost::multiprecision;
*/
#if defined(LOCAL_TEST) || defined(LOCAL_DEV)
	#define BOOST_STACKTRACE_USE_ADDR2LINE
	#define BOOST_STACKTRACE_ADDR2LINE_LOCATION /usr/local/opt/binutils/bin/addr2line
	#define _GNU_SOURCE 1
	#include <boost/stacktrace.hpp>
#endif
#ifdef LOCAL_TEST
	namespace std {
		template<typename T> class dvector : public std::vector<T> {
		public:
			dvector() : std::vector<T>() {}
			explicit dvector(size_t n, const T& value = T()) : std::vector<T>(n, value) {}
			dvector(const std::vector<T>& v) : std::vector<T>(v) {}
			dvector(const std::initializer_list<T> il) : std::vector<T>(il) {}
			template <typename Itr> dvector(const Itr first, const Itr last) : std::vector<T>(first, last) {}
			template <typename T_ = T, typename std::enable_if_t<std::is_same_v<T_, bool>, std::nullptr_t> = nullptr>
			std::vector<bool>::reference operator[](size_t n) {
				if (this->size() <= n) { std::cerr << boost::stacktrace::stacktrace() << '\n' << "vector::_M_range_check: __n (which is " << n << ") >= this->size() (which is " << this->size() << ")" << '\n'; } return this->at(n);
			}
			template <typename T_ = T, typename std::enable_if_t<std::is_same_v<T_, bool>, std::nullptr_t> = nullptr>
			const T_ operator[](size_t n) const {
				if (this->size() <= n) { std::cerr << boost::stacktrace::stacktrace() << '\n' << "vector::_M_range_check: __n (which is " << n << ") >= this->size() (which is " << this->size() << ")" << '\n'; } return this->at(n);
			}
			template <typename T_ = T, typename std::enable_if_t<!std::is_same_v<T_, bool>, std::nullptr_t> = nullptr>
			T_& operator[](size_t n) {
				if (this->size() <= n) { std::cerr << boost::stacktrace::stacktrace() << '\n' << "vector::_M_range_check: __n (which is " << n << ") >= this->size() (which is " << this->size() << ")" << '\n'; } return this->at(n);
			}
			template <typename T_ = T, typename std::enable_if_t<!std::is_same_v<T_, bool>, std::nullptr_t> = nullptr>
			const T_& operator[](size_t n) const {
				if (this->size() <= n) { std::cerr << boost::stacktrace::stacktrace() << '\n' << "vector::_M_range_check: __n (which is " << n << ") >= this->size() (which is " << this->size() << ")" << '\n'; } return this->at(n);
			}
		};
		template<typename T, typename Compare = std::less<T>, typename Allocator = std::allocator<T>> class dmultiset : public std::multiset<T,Compare,Allocator> {
		public:
			dmultiset() : std::multiset<T,Compare,Allocator>() {}
			dmultiset(const std::multiset<T,Compare,Allocator>& m) : std::multiset<T,Compare,Allocator>(m) {}
			dmultiset(const std::initializer_list<T> il) : std::multiset<T,Compare,Allocator>(il) {}
			dmultiset(const Compare& comp) : std::multiset<T,Compare,Allocator>(comp) {}
			const typename std::multiset<T,Compare,Allocator>::iterator erase(const typename std::multiset<T,Compare,Allocator>::iterator it) {
				return std::multiset<T,Compare,Allocator>::erase(it);
			}
			size_t erase([[maybe_unused]] const T& x) {
				std::cerr << boost::stacktrace::stacktrace() << '\n'; assert(false);
			}
			size_t erase_all_elements(const T& x) {
				return std::multiset<T,Compare,Allocator>::erase(x);
			}
		};
	}
	#define vector dvector
	#define multiset dmultiset
	class SIGFPE_exception : std::exception {};
	class SIGSEGV_exception : std::exception {};
	void catch_SIGFPE([[maybe_unused]] int e) { std::cerr << boost::stacktrace::stacktrace() << '\n'; throw SIGFPE_exception(); }
	void catch_SIGSEGV([[maybe_unused]] int e) { std::cerr << boost::stacktrace::stacktrace() << '\n'; throw SIGSEGV_exception(); }
	signed convertedmain();
	signed main() { signal(SIGFPE, catch_SIGFPE); signal(SIGSEGV, catch_SIGSEGV); return convertedmain(); }
	#define main() convertedmain()
#else
	#define erase_all_elements erase
#endif
#ifdef LOCAL_DEV
	template<typename T1, typename T2> std::ostream& operator<<(std::ostream& s, const std::pair<T1, T2>& p) {
		return s << "(" << p.first << ", " << p.second << ")"; }
	template <typename T, size_t N> std::ostream& operator<<(std::ostream& s, const std::array<T, N>& a) {
		s << "{ "; for (size_t i = 0; i < N; ++i){ s << a[i] << "\t"; } s << "}"; return s; }
	template<typename T> std::ostream& operator<<(std::ostream& s, const std::set<T>& se) {
		s << "{ "; for (auto itr = se.begin(); itr != se.end(); ++itr){ s << (*itr) << "\t"; } s << "}"; return s; }
	template<typename T> std::ostream& operator<<(std::ostream& s, const std::multiset<T>& se) {
		s << "{ "; for (auto itr = se.begin(); itr != se.end(); ++itr){ s << (*itr) << "\t"; } s << "}"; return s; }
	template<typename T1, typename T2> std::ostream& operator<<(std::ostream& s, const std::map<T1, T2>& m) {
		s << "{\n"; for (auto itr = m.begin(); itr != m.end(); ++itr){ s << "\t" << (*itr).first << " : " << (*itr).second << "\n"; } s << "}"; return s; }
	template<typename T> std::ostream& operator<<(std::ostream& s, const std::deque<T>& v) {
		for (size_t i = 0; i < v.size(); ++i){ s << v[i]; if (i < v.size() - 1) s << "\t"; } return s; }
	template<typename T> std::ostream& operator<<(std::ostream& s, const std::vector<T>& v) {
		for (size_t i = 0; i < v.size(); ++i){ s << v[i]; if (i < v.size() - 1) s << "\t"; } return s; }
	template<typename T> std::ostream& operator<<(std::ostream& s, const std::vector<std::vector<T>>& vv) {
		s << "\\\n"; for (size_t i = 0; i < vv.size(); ++i){ s << vv[i] << "\n"; } return s; }
	void debug_impl() { std::cerr << '\n'; }
	template<typename Head, typename... Tail> void debug_impl(Head head, Tail... tail) { std::cerr << " " << head << (sizeof...(tail) ? "," : ""); debug_impl(tail...); }
	#define debug(...) do { std::cerr << ":" << __LINE__ << " (" << #__VA_ARGS__ << ") ="; debug_impl(__VA_ARGS__); } while (false)
	constexpr inline long long prodlocal([[maybe_unused]] long long prod, [[maybe_unused]] long long local) { return local; }
#else
	#define debug(...) do {} while (false)
	constexpr inline long long prodlocal([[maybe_unused]] long long prod, [[maybe_unused]] long long local) { return prod; }
#endif
//#define int long long
using ll = long long;
//INT_MAX = (1<<31)-1 = 2147483647, INT64_MAX = (1LL<<63)-1 = 9223372036854775807
constexpr ll INF = numeric_limits<ll>::max() == INT_MAX ? (ll)1e9 + 7 : (ll)1e18;
//constexpr ll MOD = (ll)1e9 + 7; //primitive root = 5
//constexpr ll MOD = 998244353; //primitive root = 3
constexpr double EPS = 1e-9;
constexpr ll dx[4] = {1, 0, -1, 0};
constexpr ll dy[4] = {0, 1, 0, -1};
constexpr ll dx8[8] = {1, 0, -1, 0, 1, 1, -1, -1};
constexpr ll dy8[8] = {0, 1, 0, -1, 1, -1, 1, -1};
#define rep(i, n)   for(ll i=0, i##_length=(n); i< i##_length; ++i)
#define repeq(i, n) for(ll i=1, i##_length=(n); i<=i##_length; ++i)
#define rrep(i, n)   for(ll i=(n)-1; i>=0; --i)
#define rrepeq(i, n) for(ll i=(n)  ; i>=1; --i)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
void p() { std::cout << '\n'; }
template<typename Head, typename... Tail> void p(Head head, Tail... tail) { std::cout << head << (sizeof...(tail) ? " " : ""); p(tail...); }
template<typename T> inline void pv(std::vector<T>& v) { for(ll i=0, N=v.size(); i<N; i++) std::cout << v[i] << " \n"[i==N-1]; }
template<typename T> inline bool chmax(T& a, T b) { return a < b && (a = b, true); }
template<typename T> inline bool chmin(T& a, T b) { return a > b && (a = b, true); }
template<typename T> inline void uniq(std::vector<T>& v) { v.erase(std::unique(v.begin(), v.end()), v.end()); }
template<typename T> inline ll sz(T& v) { return v.size(); }
template<typename T, size_t N> std::vector<T> make_vector_impl(std::vector<ll>& sizes, typename std::enable_if<(N==1), T const&>::type x) { return std::vector<T>(sizes.front(),x); }
template<typename T, size_t N> auto make_vector_impl(std::vector<ll>& sizes, typename std::enable_if<(N>1), T const&>::type x) { ll size=sizes.back(); sizes.pop_back(); return std::vector<decltype(make_vector_impl<T,N-1>(sizes,x))>(size,make_vector_impl<T,N-1>(sizes,x)); }
template<typename T, size_t N> auto make_vector(ll const (&sizes)[N], T const& x=T()) { std::vector<ll> s(N); for(size_t i=0; i<N; ++i)s[i]=sizes[N-1-i]; return make_vector_impl<T,N>(s,x); }

/*-----8<-----template-----8<-----*/

constexpr ll MOD = 10; //primitive root = 5
//constexpr ll MOD = (ll)1e9 + 7; //primitive root = 5

/*
map<ll,ll> inv_cache;
struct Modint{
	unsigned long long num = 0;
	constexpr Modint() noexcept {}
	//constexpr Modint(const Modint &x) noexcept : num(x.num){}
	inline constexpr operator ll() const noexcept { return num; }
	inline constexpr Modint& operator+=(Modint x) noexcept { num += x.num; if(num >= MOD) num -= MOD; return *this; }
	inline constexpr Modint& operator++() noexcept { if(num == MOD - 1) num = 0; else num++; return *this; }
	inline constexpr Modint operator++(int) noexcept { Modint ans(*this); operator++(); return ans; }
	inline constexpr Modint operator-() const noexcept { return Modint(0) -= *this; }
	inline constexpr Modint& operator-=(Modint x) noexcept { if(num < x.num) num += MOD; num -= x.num; return *this; }
	inline constexpr Modint& operator--() noexcept { if(num == 0) num = MOD - 1; else num--; return *this; }
	inline constexpr Modint operator--(int) noexcept { Modint ans(*this); operator--(); return ans; }
	inline constexpr Modint& operator*=(Modint x) noexcept { num = (unsigned long long)(num) * x.num % MOD; return *this; }
	inline Modint& operator/=(Modint x) noexcept { return operator*=(x.inv()); }
	template<class T> constexpr Modint(T x) noexcept {
		using U = typename conditional<sizeof(T) >= 4, T, int>::type;
		U y = x; y %= U(MOD); if(y < 0) y += MOD; num = (unsigned long long)(y);
	}
	template<class T> inline constexpr Modint operator+(T x) const noexcept { return Modint(*this) += x; }
	template<class T> inline constexpr Modint& operator+=(T x) noexcept { return operator+=(Modint(x)); }
	template<class T> inline constexpr Modint operator-(T x) const noexcept { return Modint(*this) -= x; }
	template<class T> inline constexpr Modint& operator-=(T x) noexcept { return operator-=(Modint(x)); }
	template<class T> inline constexpr Modint operator*(T x) const noexcept { return Modint(*this) *= x; }
	template<class T> inline constexpr Modint& operator*=(T x) noexcept { return operator*=(Modint(x)); }
	template<class T> inline constexpr Modint operator/(T x) const noexcept { return Modint(*this) /= x; }
	template<class T> inline constexpr Modint& operator/=(T x) noexcept { return operator/=(Modint(x)); }
	inline Modint inv() const noexcept { return inv_cache.count(num) ? inv_cache[num] : inv_cache[num] = inv_calc(); }
	inline constexpr ll inv_calc() const noexcept { ll x = 0, y = 0; extgcd(num, MOD, x, y); return x; }
	static inline constexpr ll extgcd(ll a, ll b, ll &x, ll &y) noexcept { ll g = a; x = 1; y = 0; if(b){ g = extgcd(b, a % b, y, x); y -= a / b * x; } return g; }
	inline constexpr Modint pow(ll x) const noexcept { Modint ans = 1, cnt = x>=0 ? *this : inv(); if(x<0) x = -x; while(x){ if(x & 1) ans *= cnt; cnt *= cnt; x /= 2; } return ans; }
	static inline constexpr ll get_mod() { return MOD; }
};
std::istream& operator>>(std::istream& is, Modint& x){ ll a; is>>a; x = a; return is; }
inline constexpr Modint operator""_M(unsigned long long x) noexcept { return Modint(x); }
std::vector<Modint> fac(1, 1), inv(1, 1);
inline void reserve(size_t a){
	if(fac.size() >= a) return;
	if(a < fac.size() * 2) a = fac.size() * 2;
	if(a >= MOD) a = MOD;
	fac.reserve(a);
	while(fac.size() < a) fac.push_back(fac.back() * Modint(fac.size()));
	inv.resize(fac.size());
	inv.back() = fac.back().inv();
	for(ll i = inv.size() - 1; !inv[i - 1]; i--) inv[i - 1] = inv[i] * i;
}
inline Modint factorial(ll n){ if(n < 0) return 0; reserve(n + 1); return fac[n]; }
inline Modint nPk(ll n, ll r){
    if(r < 0 || n < r) return 0;
    if(n >> 24){ Modint ans = 1; for(ll i = 0; i < r; i++) ans *= n--; return ans; }
    reserve(n + 1); return fac[n] * inv[n - r];
}
inline Modint nCk(ll n, ll r){ if(r < 0 || n < r) return 0; r = min(r, n - r); reserve(r + 1); return inv[r] * nPk(n, r); }
inline Modint nHk(ll n, ll r){ return nCk(n + r - 1, n - 1); } //n種類のものから重複を許してr個選ぶ=玉r個と仕切りn-1個
inline Modint catalan(ll n){ reserve(n * 2 + 1); return fac[n * 2] * inv[n] * inv[n + 1]; }
*/
/*
計算量：和, 差: O(N^2)
　　　　積: O(N^3)
　　　　行列累乗(^=k): O(N^3logk)
　　　　行列式(determinant): O(N^3)
*/
/*
https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1174464211
隣接行列Aについて、A^xの(i,j)成分は、i->jの長さxのパスの数に等しい。
A^xの(i,i)成分が0でないとき、頂点iを通る長さxのサイクルがある。
*/
template< class T >
struct Matrix {
	vector< vector< T > > A;
	static T &get_E() { static T eval = 1; return eval; }
	static void set_E(T e) { get_E() = e; }

	Matrix() {}
	Matrix(size_t n, size_t m) : A(n, vector< T >(m, 0)) {}
	Matrix(size_t n) : A(n, vector< T >(n, 0)) {};

	size_t height() const {
		return (A.size());
	}

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

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

	inline vector< T > &operator[](int k) {
		return (A.at(k));
	}

	static Matrix E(size_t n) {
		T e = get_E();
		Matrix mat(n);
		for(size_t i = 0; i < n; i++) mat[i][i] = e;
		return (mat);
	}

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

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

	Matrix &operator*=(const Matrix &B) {
		size_t n = height(), m = B.width(), p = width();
		assert(p == B.height());
		vector< vector< T > > C(n, vector< T >(m, 0));
		for(size_t i = 0; i < n; i++)
			for(size_t j = 0; j < m; j++)
				for(size_t k = 0; k < p; k++){
					C[i][j] = (C[i][j] + (*this)[i][k] * B[k][j]);
					C[i][j] %= MOD;
				}
		A.swap(C);
		return (*this);
	}

	Matrix &operator^=(long long k) {
		Matrix B = Matrix::E(height());
		while(k > 0) {
			if(k & 1) B *= *this;
			*this *= *this;
			k >>= 1LL;
		}
		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);
	}
/*
	friend ostream &operator<<(ostream &os, Matrix &p) {
		size_t n = p.height(), m = p.width();
		os << '\n';
		for (size_t i = 0; i < n; i++) {
			os << "[";
			for(size_t j = 0; j < m; j++) {
				os << p[i][j] << (j + 1 == m ? "]\n" : "\t");
			}
		}
		return (os);
	}
*/
	T determinant() {
		assert(width() == height());
		int N = width();
		T ans = 1;
		Matrix m(*this);
		for(int i = 0; i < N; i++){
			if(m[i][i] == T(0)){
				for(int j = i + 1; j < N; j++) {
					if(m[j][i] != T(0)){
						swap(m[i], m[j]);
						ans *= -1;
						break;
					}
				}
				if(m[i][i] == T(0)) return 0;
			}
			ans *= m[i][i];
			T vv = m[i][i];
			for (int j = 0; j < N; j++) {
				m[i][j] /= vv;
			}
			for (int j = i + 1; j < N; j++) {
				T a = m[j][i];
				for (int k = 0; k < N; k++) {
					m[j][k] -= m[i][k] * a;
				}
			}
		}
		return ans;
	}
};
/*-----8<-----library-----8<-----*/

void solve() {
	//using Modint = static_modint<10>;

	vector<ll> z(3);
	rep(i, 3) cin >> z[2-i];
	ll N;
	cin >> N;

	/*
	Matrix<Modint> v(3,3);
	rep(i,3)v[0][i] = 1;
	v[1][0] = v[1][2] = 1;
	v ^= (K - 3);
	*/
	ll K = 3;
	Matrix<ll> a(K, K);
	rep(i, K) a[0][i] = 1;
	rep(i, K - 1) a[i + 1][i] = 1;

	//行列累乗(^=k): O(N^3logk)
	a ^= (N - K);

	Matrix<ll> b(K);
	rep(i, K) b[i][0] = z[i];

	Matrix<ll> c = a * b;
	//debug(c);
	auto ans = c[0][0]%MOD;
	p(ans);
	//1 2 3 4 5 6 7
	//1 1 1 3 5 9 7
}

signed main() {
	std::cin.tie(nullptr);
	std::ios::sync_with_stdio(false);
	//ll Q; cin >> Q; while(Q--)solve();
	solve();
	return 0;
}
yukicoder

結果

テストケース

ソースコード
