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

• 問題: No.53 悪の漸化式
• ユーザー: a5ua
• 提出日時: 2014-11-01 23:56:16
• 言語: C++11 (gcc 11.4.0)
• 結果: WA
• 実行時間: -
• コード長: 1,129 bytes
• コンパイル時間: 421 ms
• コンパイル使用メモリ: 58,760 KB
• 実行使用メモリ: 4,380 KB
• 最終ジャッジ日時: 2023-08-29 00:13:57
• 合計ジャッジ時間: 1,426 ms
• ジャッジサーバーID （参考情報）: judge15 / judge12

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

ソースコード

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