#30260 (C++11) No.53 悪の漸化式

• 問題: No.53 悪の漸化式
• ユーザー: vain0
• 提出日時: 2015-05-31 23:29:16
• 言語: C++11 (gcc 11.4.0)
• 結果: WA
• 実行時間: -
• コード長: 3,549 bytes
• コンパイル時間: 776 ms
• コンパイル使用メモリ: 82,304 KB
• 実行使用メモリ: 4,384 KB
• 最終ジャッジ日時: 2023-09-20 18:09:56
• 合計ジャッジ時間: 1,508 ms
• ジャッジサーバーID （参考情報）: judge13 / judge15

入力	結果	実行時間; 実行使用メモリ
testcase_00	WA	-
testcase_01	WA	-
testcase_02	WA	-
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	AC	2 ms; 4,380 KB
testcase_18	AC	2 ms; 4,380 KB
testcase_19	AC	1 ms; 4,376 KB

ソースコード

#include <cassert>
#include <functional>
#include <set>
#include <ctime>
#include <cmath>
#include <climits>
#include <string>
#include <queue>
#include <map>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstdio>
#ifndef ONLINE_JUDGE //POJ
# include <random>
# include <array>
# define mkt make_tuple
# define empb emplace_back
#endif
#ifdef _LOCAL
# include "for_local.h"
#endif
using namespace std;
typedef unsigned int uint; typedef unsigned long long ull;
#define repi(_I, _B, _E) for(int _I = (_B); (_I) < (_E); ++ (_I))
#define rep(_I, _N) for(int _I = 0; (_I) < (_N); ++ (_I))
#define mkp make_pair
#define all(_X) (_X).begin(), (_X).end()
#define scani(_V) std::scanf("%d", &_V)
#define printi(_V) std::printf("%d", static_cast<int>(_V))


template<typename T>
struct AddMulRing {
	static T zero() { return 0; }
	static T one() { return 1; }
	static T add(T const& lhs, T const& rhs) { return lhs + rhs; }
	static T mul(T const& lhs, T const& rhs) { return lhs * rhs; }
	static T neg(T const& rhs) { return -rhs; }
};
template<typename T, typename Fun>
T exponent_by_squaring(T const& x, unsigned int n, T const& unit, Fun const& f) {
	if ( n == 0 ) return unit;
	if ( n == 1 ) return x;
	T z = unit;
	T w = x;
	while ( n != 0 ) {
		if ( (n & 1) != 0 ) {
			f(z, w); n ^= 1;
		} else {
			f(w, w); n >>= 1;
		}
	}
	return std::move(z);
}
template<typename TScalar, typename Ring = AddMulRing<TScalar>>
class Matrix {
	using uint = unsigned int;
	using value_type = TScalar; //scalar type

	uint rows_, cols_;
	std::vector<value_type> v_;
public:
	Matrix(uint rows, uint cols) : rows_(rows), cols_(cols), v_() { v_.resize(rows * cols, Ring::zero()); }
	Matrix(uint rows, uint cols, std::vector<value_type> v) : rows_ { rows }, cols_ { cols }, v_(std::move(v)) {
		assert(v_.size() == rows_* cols_);
	}
private:
	template<typename Fun>
	Matrix(Fun&& f, uint rows, uint cols) : rows_(rows), cols_(cols), v_ {} {
		v_.reserve(rows_ * cols_);
		for ( uint i = 0; i < rows_; ++i ) for ( uint j = 0; j < cols_; ++j ) { v_.emplace_back(f(i, j)); }
	}
public:
	template<typename Fun>
	static Matrix generate(uint rows, uint cols, Fun&& f) {
		return Matrix { std::move(f), rows, cols };
	}
	static Matrix ofScalar(uint n, value_type const& s) {
		return generate(n, n, [&s](uint i, uint j) { return (i == j ? s : Ring::zero()); });
	}
	static Matrix iden(uint n) { return ofScalar(n, Ring::one()); }
	uint rows() const { return rows_; }
	uint cols() const { return cols_; }
	value_type const& at(uint i, uint j) const {
		assert(i < rows() && j < cols());
		return v_[i * cols() + j];
	}
	value_type& at(uint i, uint j) { return const_cast<value_type&>(const_cast<Matrix const*>(this)->at(i, j)); }

	Matrix operator*(Matrix const& rhs) const {
		Matrix const& lhs = *this;
		assert(lhs.cols() == rhs.rows());
		return generate(lhs.rows(), rhs.cols(), [&lhs, &rhs](uint i, uint j) {
			auto x = Ring::zero();
			for (uint t = 0; t < lhs.cols(); ++t) {
				x = Ring::add(x, Ring::mul(lhs.at(i, t), rhs.at(t, j)));
			}
			return x;
		});
	}
	Matrix& operator*=(Matrix const& rhs) { return (*this) = (*this) * rhs; }

	Matrix pow(uint n) const {
		assert(rows() == cols());
		return exponent_by_squaring(*this, n, iden(rows()),
			[](Matrix& lhs, Matrix const& rhs) { lhs *= rhs; });
	}
};

double calc(int n) {
	Matrix<double> t(2, 2, { 19.0 / 4, -3, 1.0, 0 }),
		s(2, 1, { 3, 4 });
	auto tn = t.pow(n);

	return (tn * s).at(1, 0);
}

signed main() {
	int n;
	cin >> n;
	double d = calc(n);
	printf("%.10llf", d);
	return 0;
}