[SPOJ] KPGAME

I assume this fact (seems reasonable although I could not prove it):

- If N is odd: taking a coin is always better
- If N is even: not taking a coin is always better

Let $F_N$ be the probability that the first player will win if there are N stones

With the above fact, we can derive the recurrence formula for $F_N$:

$\footnotesize{F_N = \begin{cases}
P[QF_{N-1} + (1-Q)F_{N-2}]+ (1-P)[QF_{N-1}+(1-Q)F_N)]& \text{ if N is odd} \\
(1-P)[(1-Q)F_{N-1}+QF_{N-2}]+ P[(1-Q)F_{N-1} + QF_N]& \text{ if N is even}
\end{cases}}$

$\footnotesize{F_N = \begin{cases}
QF_{N-1} + P(1-Q)F_{N-2} + (1-P)(1-Q)F_N & \text{ if N is odd} \\
(1-Q)F_{N-1}+(1-P)QF_{N-2} + PQF_N& \text{ if N is even}
\end{cases}}$

$\small{F_N = \begin{cases}
\frac{QF_{N-1} + P(1-Q)F_{N-2}}{1-(1-P)(1-Q)} & \text{ if N is odd} \\ \\
\frac{(1-Q)F_{N-1}+(1-P)QF_{N-2}}{1-PQ}& \text{ if N is even}
\end{cases}}$

Let's use matrix multiplication to compute $F_N$ quickly. We have:

$\begin{bmatrix}
F_N\\
F_{N-1}
\end{bmatrix}
=
\begin{cases}
\begin{bmatrix}
\frac{Q}{1-(1-P)(1-Q)}& \frac{P(1-Q)}{1-(1-P)(1-Q)}\\
1 & 0
\end{bmatrix}
\begin{bmatrix}
F_{N-1}\\
F_{N-2}
\end{bmatrix} & \text{ if N is odd}
\\
\\
\begin{bmatrix}
\frac{1-Q}{1-PQ}& \frac{(1-P)Q}{1-PQ}\\
1 & 0
\end{bmatrix}
\begin{bmatrix}
F_{N-1}\\
F_{N-2}
\end{bmatrix} & \text{ if N is even}
\end{cases}$

And:
$\begin{bmatrix}
F_N\\
F_{N-1}
\end{bmatrix}
=
\begin{cases}

AB^{\frac{N-1}{2}}
\begin{bmatrix}
F_1 \\
F_0
\end{bmatrix} & \text{ if N is odd}
\\
\\
B(AB)^{\frac{N}{2}-1}
\begin{bmatrix}
F_1 \\
F_0
\end{bmatrix} & \text{ if N is even}
\end{cases}$

Where A is the first matrix and B is the second matrix.

Base case:
$\begin{bmatrix}
F_1 \\
F_0
\end{bmatrix}
=
\begin{bmatrix}
\frac{P}{1-(1-P)(1-Q)} \\
0
\end{bmatrix}$

Implementation: calculation up to N = 10^8 would cause floating points error and using arbitrary length arithmetic would be too slow (e.g. Python's decimal). Trick: let N = min(N, 1000+N%2), the answer wouldn't be much different.