https://beta.atcoder.jp/contests/code-festival-2014-morning-middle/tasks/code_festival_morning_med_c

誤差死して悔しかったのでまとめておく

概要

eject工作をしてスイッチを押す機械を作ったが、1回の開閉につき確率pでしかスイッチを押せない
n回開閉した結果、初期状態がOFFのスイッチがONになっている確率を求める

制約

  • $ n \le 10^{18} $
  • $ 0 \le p \le 1 $ 小数第10位まで与えられる
  • 出力 絶対/相対誤差のうち少なくとも片方が$ 10^{−6} $以下

$O(\log{N})$ 誤差死解法 doubling

$2^k$回開閉した結果を計算したのち、nの2進展開に基づき計算
__float128(GCC拡張)で計算すれば通る

これしか思いつけず、かつ__float128どころかlong doubleも知らなかったのでだめだった

$O(\log{N})$ 解法 doubling + 正規化

任意の時点で、ONである確率onとOFFである確率offはon + off = 1を満たす よって、(offを1 - onという形でなく別個に求めて)

on'  = on  / (on + off)
off' = off / (on + off)

という処理を挟めば精度が向上する
doubleでもACできる

$O(1)$ 解法 数学

二項定理を用いる
スイッチが奇数回押されればONであるので、

\[\mathrm{on} = \sum_{i=1,3,\cdots}^n {}_n\mathrm{C}_i p^i (1-p)^{n-i} \\ \mathrm{off} = \sum_{i=0,2,\cdots}^n {}_n\mathrm{C}_i p^i (1-p)^{n-i}\]

すると偶奇性より

\[(+ p + (1 - p))^n = + \mathrm{on} + \mathrm{off} \\ (- p + (1 - p))^n = - \mathrm{on} + \mathrm{off}\]

変形し

\[(1 - 2p)^n = 1 - 2on \\ \mathrm{on} = \frac{1 - (1 - 2p)^n}{2}\]

cmathのpowは魔法のようなアルゴリズムにより$O(1)$らしく、1行で求まってしまう
long doubleでACできる (doubleはWAした)