結果

問題 No.53 悪の漸化式
ユーザー yumakmcyumakmc
提出日時 2016-04-25 14:47:23
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,432 bytes
コンパイル時間 1,295 ms
コンパイル使用メモリ 167,452 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-04-15 04:26:37
合計ジャッジ時間 1,970 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 1 ms
6,944 KB
testcase_06 AC 1 ms
6,944 KB
testcase_07 AC 1 ms
6,940 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 1 ms
6,940 KB
testcase_10 AC 1 ms
6,944 KB
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 -
権限があれば一括ダウンロードができます

ソースコード

diff # 



#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;

template<typename T>
vector<vector<T>> keisann(const vector<vector<T>>l, const vector<vector<T>>r) {
	vector<vector<T>>ans(l.size(), vector<T>(r[0].size()));
	assert(l[0].size() == r.size());
	for (unsigned int h = 0; h < l.size(); ++h) {
		for (unsigned int i = 0; i < r.size(); ++i) {
			for (unsigned int w = 0; w < r[0].size(); ++w) {

				ans[h][w] += l[h][i] * r[i][w];
			}
		}
	}
	return ans;
}

template<typename T>
vector<vector<T>>powgyou(vector<vector<T>>a, const long long int n) {
	assert(a.size() == a[0].size());
	if (!n) {
		vector<vector<T>>e(a.size(), vector<T>(a[0].size()));
		for (unsigned int i = 0; i < a.size(); ++i) {
			e[i][i] = 1;
		}
		return e;
	}
	if (n == 1)return a;
	else {
		vector<vector<T>>ans(a.size(), vector<T>(a[0].size(), 0));
		ans = powgyou(a, n / 2);
		ans = keisann(ans, ans);
		if (n % 2) {
			ans = keisann(ans, a);
		}
		return ans;
	}
}
int main() {
	int N; cin >> N;
	vector<vector<ld>>mat(2, vector<ld>(2));
	mat[0][0] = 4.75;
	mat[0][1] = -3;
	mat[1][0] = 1;
	mat[1][1] = 0;
	vector<vector<ld>>from(2, vector<ld>(1));
	from[0][0] = 3;
	from[1][0] = 4;
	vector<vector<ld>>ans = keisann(powgyou(mat, N), from);
	cout <<fixed<<setprecision(22)<< ans[1][0] << endl;
	return 0;
}
0