#1176061 (D) No.301 サイコロで確率問題 (1)

• 問題: No.301 サイコロで確率問題 (1)
• ユーザー: ゴリポン先生
• 提出日時: 2026-08-10 19:31:10
• 言語: D (dmd 2.112.0)
• 結果: AC
• 実行時間: 89 ms / 1,000 ms
• コード長: 3,460 bytes
• コンパイル時間: 5,797 ms
• コンパイル使用メモリ: 201,344 KB
• 実行使用メモリ: 5,888 KB
• 最終ジャッジ日時: 2026-08-10 19:31:18
• 合計ジャッジ時間: 5,752 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
other	AC * 2

ソースコード

module main;
// https://pekempey.hatenablog.com/entry/2015/11/15/184235 より
// 確率、動的計画法、行列
import std;

// https://ei1333.github.io/library/math/matrix/matrix.hpp より
struct Matrix(T) {
	T[][] A;
	alias A this;
	// コンストラクタ
	this(size_t n, size_t m)
	{
		A = new T[][](n, m);
		static if (T.init != 0)
			foreach (ref a; A)
				a[] = 0;
	}
	this(size_t n)
	{
		A = new T[][](n, n);
		static if (T.init != 0)
			foreach (ref a; A)
				a[] = 0;
	}
	// 行数
	size_t height() const
	{
		return A.length;
	}
	// 列数
	size_t width() const
	{
		return A[0].length;
	}
	// 単位行列
	static Matrix I(size_t n)
	{
		auto mat = Matrix(n);
		static if (T.init != 0)
			foreach (ref m; mat)
				m[] = 0;
		foreach (i; 0 .. n) mat[i][i] = 1;
		return mat;
	}
	/*
	 * 演算代入演算子
	 */
	// 加減算
	Matrix opOpAssign(string op)(Matrix B)
		if (op == "+" || op == "-")
	{
		size_t n = height(), m = width();
		assert(n == B.height() && m == B.width());
		foreach (i; 0 .. n)
			foreach (j; 0 .. m) mixin("A[i][j] " ~ op ~ "= B[i][j]");
		return this;
	}
	// 掛け算
	Matrix opOpAssign(string op : "*")(Matrix B)
	{
		size_t n = height(), m = B.width(), p = width();
		assert(p == B.height());
		auto C = new T[][](n, m);
		static if (T.init != 0)
			foreach (ref c; C)
				c[] = 0;
		foreach (i; 0 .. n)
			foreach (j; 0 .. m)
				foreach (k; 0 .. p)
					C[i][j] += A[i][k] * B[k][j];
		swap(A, C);
		return this;
	}
	// 累乗
	Matrix opOpAssign(string op : "^^")(long k)
	{
		auto B = I(height());
		while (k > 0) {
			if (k & 1) B *= this;
			this *= this;
			k >>= 1;
		}
		swap(A, B.A);
		return this;
	}
	/*
	 * 二項演算子
	 */
	Matrix opBinary(string op)(Matrix B)
		if (op == "+" || op == "-" || op == "*")
	{
		Matrix r = this;
		mixin("return r " ~ op ~ "= B;");
	}
	Matrix opBinary(string op : "^^")(long k)
	{
		Matrix r = this;
		return r ^^= k;
	}
	// 標準出力
	string toString() const
	{
		return format("%s", A);
	}
	// 行列式
	T determinant()
	{
		Matrix B = this;
		assert(width() == height());
		T ret = 1;
		foreach (i; 0 .. width().to!int) {
			int idx = -1;
			foreach (j; i .. width().to!int) {
				if (B[j][i] != 0) idx = j;
			}
			if (idx == -1) return 0;
			if (i != idx) {
				ret = -ret;
				swap(B[i], B[idx]);
			}
			ret *= B[i][i];
			T vv = B[i][i];
			foreach (j; 0 .. width()) {
				B[i][j] /= vv;
			}
			foreach (j; i + 1 .. width()) {
				T a = B[j][i];
				foreach (k; 0 .. width()) {
					B[j][k] -= B[i][k] * a;
				}
			}
		}
		return ret;
	}
}
alias Mat = Matrix!double;
// モニック多項式からフロベニウスの同伴行列を求める
void companion(inout(double)[] a, ref Mat res)
{
	auto n = a.length;
	foreach (i; 0 .. n - 1) res[i][i + 1] = 1;
	res[n - 1][0 .. n] = a[0 .. n];
	res[n][1] = res[n][n] = 1;
}

void main()
{
	// 入力・前処理
	int T = readln.chomp.to!int;
	immutable p = 1.0 / 6;
	auto M4 = Mat(8);
	companion([p].replicate(6), M4);
	auto Mp = [Mat(8)].replicate(80);
	foreach (i; 0 .. 7)
		foreach (j; 0 .. 7)
			Mp[1][i][j] = M4[i][j];
	foreach (i; 1 .. 70) {
		Mp[i + 1] = Mp[i] * Mp[i];
	}
	// クエリの処理
	foreach (_; 0 .. T) {
		// 入力
		auto N = readln.chomp.to!long;
		// 答えの計算と出力
		if (N < 1000) {
			Mat M3 = M4 ^^ (N + 4);
			double s = M3[6][4], t = M3[6][5];
			double ans = t / (s - t * 5.0 / 6.0);
			writefln("%.12f", ans);
		} else {
			writeln(N + 1, ".666666666666");
		}
	}
}