結果

問題 No.53 悪の漸化式
ユーザー vain0vain0
提出日時 2015-05-31 23:29:16
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 3,549 bytes
コンパイル時間 587 ms
コンパイル使用メモリ 81,480 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-06 13:05:16
合計ジャッジ時間 1,221 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 WA -
testcase_18 WA -
testcase_19 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:124:23: warning: use of ‘ll’ length modifier with ‘f’ type character has either no effect or undefined behavior [-Wformat=]
  124 |         printf("%.10llf", d);
      |                       ^

ソースコード

diff # 

#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;
}
0