ユキちゃんの冒険 [yukicoder No.813]

https://yukicoder.me/problems/no/813

解説

https://yukicoder.me/submissions/338365

公式解説にもあるが、門を1つにまとめ上げることで答えを求めよう。
逃走率p1、通過率q1の門、逃走率p2、通過率q2の門を1つにまとめると、

逃走率 p=(p1+q1*q1*p2/(1-p1*p2))
通過率 q=q1*q2/(1-p1*p2)

となる。これを繰り返して、N個の門を1つにすればいい。
想定解では二分累乗法（繰り返し二乗法）が紹介されているが、
N≦10^3なので、愚直に計算しても間に合う。
N≦10^18の場合は二分累乗法が要求される。

int N; double P, Q;
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> P >> Q;

	if (P == 1) {
		printf("1\n");
		return;
	}

	double p = P, q = Q;

	rep(i, 0, N - 1) {
		double p1 = p, p2 = P;
		double q1 = q, q2 = Q;

		p = p1 + q1 * q1 * p2 / (1.0 - p1 * p2);
		q = q1 * q2 / (1.0 - p1 * p2);
	}

	printf("%.10f\n", p);
}