So Many Dice

解説

$(0 \leq x \leq K)$ における各 $x$ についての $P(x)$ の値を愚直に計算していては、実行時間制限に間に合いません。(仮に間に合ったとしても小数誤差の影響が無視できません。)そこで、計算量を落とすための工夫を考えてみます。

まず、$\displaystyle p = \frac{A}{N}$ とすると、 $\displaystyle P(x) = {}_KC_{x} p^x(1-p)^{K-x}$ と表せます。

このとき $(0 \leq x \leq K-1)$ において、 $\displaystyle f(x) = \frac{P(x+1)}{P(x)}$ の値を考えると、

$\displaystyle f(x) = \frac{P(x+1)}{P(x)} = \frac{{}_KC_{x+1}p^{x+1}(1-p)^{K-x-1}}{{}_KC_{x}p^{x}(1-p)^{K-x}} = \frac{(K-x)p}{(x+1)(1-p)}$

となり、この値は $(0 \leq x \leq K-1)$ において単調減少であることから$P(x+1) > P(x) \Longleftrightarrow f(x) > 1$ を利用して $P(x)$ が最大となる $x$ の値の範囲を二分探索で絞りこむことができます。最終的に残った範囲の左端が答えとなり、これは1クエリ当たり時間計算量 $O(logK)$ で求められるため実行時間制限に間に合います。