結果

問題 No.53 悪の漸化式
ユーザー a5uaa5ua
提出日時 2014-11-01 23:56:16
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,129 bytes
コンパイル時間 379 ms
コンパイル使用メモリ 59,040 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-09 18:41:52
合計ジャッジ時間 1,072 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

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