結果

問題 No.301 サイコロで確率問題 (1)
ユーザー FF256grhyFF256grhy
提出日時 2020-05-01 01:39:09
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 49 ms / 1,000 ms
コード長 4,224 bytes
コンパイル時間 2,178 ms
コンパイル使用メモリ 180,944 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-12-21 09:59:45
合計ジャッジ時間 3,232 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 44 ms
6,820 KB
testcase_01 AC 49 ms
6,820 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using LL = long long int;
#define incID(i, l, r) for(int i = (l)    ; i <  (r); ++i)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); --i)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); ++i)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); --i)
#define inc(i, n)  incID(i, 0, n)
#define dec(i, n)  decID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define dec1(i, n) decII(i, 1, n)
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))
#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define FR front()
#define BA back()
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
auto setmin   = [](auto & a, auto b) { return (b <  a ? a = b, true : false); };
auto setmax   = [](auto & a, auto b) { return (b >  a ? a = b, true : false); };
auto setmineq = [](auto & a, auto b) { return (b <= a ? a = b, true : false); };
auto setmaxeq = [](auto & a, auto b) { return (b >= a ? a = b, true : false); };
#define SI(v) static_cast<int>(v.size())
#define RF(e, v) for(auto & e: v)
#define until(e) while(! (e))
#define if_not(e) if(! (e))
#define ef else if
#define UR assert(false)
#define IN(T, ...) T __VA_ARGS__; IN_(__VA_ARGS__);
void IN_() { };
template<typename T, typename ... U> void IN_(T & a, U & ... b) { cin >> a; IN_(b ...); };
template<typename T> void OUT(T && a) { cout << a << endl; }
template<typename T, typename ... U> void OUT(T && a, U && ... b) { cout << a << " "; OUT(b ...); }

// ---- ----

template<typename T, int N> struct Matrix {
	vector<vector<T>> v;
	Matrix(T t) {
		init();
		inc(i, N) { v[i][i] = t; }
	}
	Matrix(vector<vector<T>> const & w = { }) { init(w); }
	void init(vector<vector<T>> const & w = { }) {
		v = vector<vector<T>>(N, vector<T>(N, 0));
		assert(w.size() <= N);
		inc(i, w.size()) { assert(w[i].size() <= N);
		inc(j, w[i].size()) {
			v[i][j] = w[i][j];
		}
		}
	}
	vector<T> const & operator[](int i) const { return v[i]; }
	vector<T>       & operator[](int i)       { return v[i]; }
	friend Matrix operator+(Matrix const & a, Matrix const & b) {
		Matrix c;
		inc(i, N) {
		inc(j, N) {
			c[i][j] = a[i][j] + b[i][j];
		}
		}
		return c;
	}
	friend Matrix operator-(Matrix const & a, Matrix const & b) {
		Matrix c;
		inc(i, N) {
		inc(j, N) {
			c[i][j] = a[i][j] - b[i][j];
		}
		}
		return c;
	}
	friend Matrix operator*(Matrix const & a, Matrix const & b) {
		Matrix c;
		inc(i, N) {
		inc(j, N) {
		inc(k, N) {
			c[i][j] += a[i][k] * b[k][j];
		}
		}
		}
		return c;
	}
	friend Matrix operator^(Matrix const & a, LL b) {
		Matrix c(1), e = a; assert(b >= 0);
		while(b) { if(b & 1) { c *= e; } e *= e; b >>= 1; }
		return c;
	}
	friend Matrix & operator+=(Matrix & a, Matrix const & b) { return (a = a + b); }
	friend Matrix & operator-=(Matrix & a, Matrix const & b) { return (a = a - b); }
	friend Matrix & operator*=(Matrix & a, Matrix const & b) { return (a = a * b); }
	friend Matrix & operator^=(Matrix & a, LL             b) { return (a = a ^ b); }
	friend ostream & operator<<(ostream & os, Matrix const & m) {
		inc(i, N) {
		inc(j, N) {
			os << m[i][j] << " ";
		} os << endl;
		} return os;
	}
};

// ----

using LD = long double;
int main() {
	LD p = 1 / 6.0L;
	Matrix<LD, 12> v{ { { 1 } } }, a{ {
		{ p, p, p, p, p, p,   p, p, p, p, p, p },
		{ 1, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0 },
		{ 0, 1, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0 },
		{ 0, 0, 1, 0, 0, 0,   0, 0, 0, 0, 0, 0 },
		{ 0, 0, 0, 1, 0, 0,   0, 0, 0, 0, 0, 0 },
		{ 0, 0, 0, 0, 1, 0,   0, 0, 0, 0, 0, 0 },
		
		{ 0, 0, 0, 0, 0, 0,   p, p, p, p, p, p },
		{ 0, 0, 0, 0, 0, 0,   1, 0, 0, 0, 0, 0 },
		{ 0, 0, 0, 0, 0, 0,   0, 1, 0, 0, 0, 0 },
		{ 0, 0, 0, 0, 0, 0,   0, 0, 1, 0, 0, 0 },
		{ 0, 0, 0, 0, 0, 0,   0, 0, 0, 1, 0, 0 },
		{ 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 1, 0 },
	} };
	auto f = [&](LL n) -> LD {
		auto w = v * (a ^ n);
		LD P = w[0][0], E = w[0][6], PP = 1 - P, EE = 0;
		incID(i, 1, 6) { EE += w[0][6 + i]; }
		return (1 / P - 1) * EE / PP + E / P;
	};
	
	vector<LD> ans;
	inc(i, 100) { ans.PB(f(i)); }
	
	cout.precision(20);
	IN(int, t);
	inc(i, t) {
		IN(LL, n);
		OUT(n < 100 ? ans[n] : n + 5 / 3.0L );
	}
}
0