結果
問題 | No.53 悪の漸化式 |
ユーザー | yumakmc |
提出日時 | 2016-04-25 14:47:23 |
言語 | C++11 (gcc 11.4.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,432 bytes |
コンパイル時間 | 1,287 ms |
コンパイル使用メモリ | 168,072 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-04 15:42:35 |
合計ジャッジ時間 | 2,108 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,820 KB |
testcase_01 | AC | 2 ms
6,816 KB |
testcase_02 | AC | 1 ms
6,816 KB |
testcase_03 | AC | 1 ms
6,820 KB |
testcase_04 | AC | 2 ms
6,816 KB |
testcase_05 | AC | 2 ms
6,816 KB |
testcase_06 | AC | 1 ms
6,820 KB |
testcase_07 | AC | 1 ms
6,816 KB |
testcase_08 | AC | 2 ms
6,816 KB |
testcase_09 | AC | 1 ms
6,816 KB |
testcase_10 | AC | 1 ms
6,816 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 | - |
ソースコード
#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; }