次数が「表の個数」、係数が「その確率」を表すような多項式 \(f(x)\) を、次のように考えることができます。

\[f(x)=((1-p_1)+p_1x)((1-p_2)+p_2x) \cdots((1-p_N)+p_Nx) = \displaystyle\prod_{i=1}^N((1-p_i)+p_ix)\]

この式を展開し、係数を \(x^{\lceil \frac{N}{2}\rceil}\) から \(x^N\) まで足したもの（すなわち \(\displaystyle\sum_{k=\lceil \frac{N}{2}\rceil}^N [x^k]f(x)\) ）が答です。

更に、形式的べき級数では \(1-x\) で割ることで係数の累積和が実現できるため、 \(g(x)=\frac{f(x)}{1-x}\) として、 \([x^N]g(x) - [x^{\lceil \frac{N}{2}\rceil-1}]g(x)\) とすることでも答を得ることができます。

計算量は、積の計算を愚直に行うと \(O(N^2)\)、高速な畳み込み＋分割統治を使うと \(O(N \log^2N)\) です。

本問題は係数が浮動小数点数であるため、ACLなどで採用されている数論変換(NTT)に基づく畳み込みは使えません。高速フーリエ変換(FFT)による畳み込みが必要になります。