CODE FESTIVAL 2014 あさプロHard : A - eject

ちょっと精度が厳しい。
http://code-festival-2014-morning-hard.contest.atcoder.jp/tasks/code_festival_morning_med_c

問題

初期状態で電源はオフである。
１回操作を行うと、確率pで電源のオンオフが切り替わる。
N回操作を行った後、電源がオンである確率を求めよ。

解法

愚直に行おうとすると、N回中電源オンオフがi回切り替わる確率はなので、iが奇数のものだけ足せばよいことになる。
しかし今回Nの上限が大きいのでこんなことはやっていられない。

そこで以下のようにN回を半々に分割していく。
確率pのスイッチをx回操作した後、電源が奇数回切り替わる確率をf(p,x)とする。

• xが偶数のとき:
  • x/2回スイッチを操作することを２セット行い、どちらか片方だけ奇数回切り替わればよいので
  • f(p,x) = f(p,x/2)*(1-f(p,x/2)) + (1-f(p,x/2))*f(p,x/2) = 2*f(p,x/2)*(1-f(p,x/2))
• xが奇数のとき:
  • x/2回スイッチを操作することを２セット行い、さらにあと１回スイッチを操作して、計３セット中１回または３回だけ奇数回切り替わればよいので
  • f(p,x) = 2*f(p,x/2)*(1-f(p,x/2))*(1-p) + (f(p,x/2)^2 + (1-f(p,x/2))^2) * p

あとはf(p,N)を求めれば答え。
doubleだと精度が危ないので、long doubleを使うと良い。

long double prob(long double p, ll v) {
	if(v==0) return 0;
	if(v==1) return p;
	long double pp=prob(p,v/2);
	
	if(v%2==0) return 2*pp*(1-pp);
	else return 2*pp*(1-pp)*(1-p)+(pp*pp+(1-pp)*(1-pp))*p;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	long double P;
	ll N;
	cin>>P>>N;
	_P("%.12Lf\n",prob(P,N));

まとめ

一瞬迷ったが、思いついた後はあっさり解けた。