結果

問題 No.53 悪の漸化式
ユーザー a5ua
提出日時 2014-11-01 23:56:16
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 1,129 bytes
コンパイル時間 1,354 ms
コンパイル使用メモリ 57,436 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-30 16:10:38
合計ジャッジ時間 1,349 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 13 WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>

using namespace std;

struct matrix2x2
{
	double e[2][2];
};

matrix2x2 multiply(const matrix2x2 &a, const matrix2x2 &b)
{
	matrix2x2 c;
	for (int i = 0; i < 2; ++i) {
		for (int j = 0; j < 2; ++j) {
			c.e[i][j] = 0;
			for (int k = 0; k < 2; ++k) {
				c.e[i][j] += a.e[i][k] * b.e[k][j];
			}
		}
	}
	return c;
}

template <typename T>
struct num_traits
{
	static T identity_element();
};

template <>
struct num_traits<matrix2x2>
{
	static matrix2x2 identity_element()
	{
		matrix2x2 u = {
			{
				{1, 0}, 
				{0, 1}, 
			}
		};
		return u;
	}
};

template <typename T, typename Mul>
T power(T x, unsigned int n, Mul mul)
{
	if (n == 0) {
		return num_traits<T>::identity_element();
	} else if (n & 1) {
		return mul(x, power(x, n - 1, mul));
	} else {
		auto t = power(x, n / 2, mul);
		return mul(t, t);
	}
}


int main()
{
	int N;
	cin >> N;
	matrix2x2 A = {
		{
			{19.0 / 4, -3}, 
			{1, 0}, 
		}
	};
	auto B = power(A, N, multiply);
	double ans = B.e[1][0] * 3 + B.e[1][1] * 4;
	printf("%.10f\n", ans);
}
0