[SPOJ] MYSTIC

Let N be the number of types.

We have S trials and N types. N must occur $u \geq need[N]$ times in the sequence of trials. Removing these occurrences of N, we obtain a subproblem with S-u trials and N-1 types. This lead us to the following DP solution:

Let C(S,T) be the number of outcomes to satisfy the first S types when we have T trials. We have:
$C(S,T) = \sum_{u \geq need[S]}{_{u}^{T}{C}\times C(S-1,T-u)}$

We would like to compute the probability, not the cardinality C(S,T).
Let $F(S,T) = \frac{C(S,T)}{N^T}$
We have:
$F(S,T) = \frac{\sum_{u \geq need[S]}{_{u}^{T}C\times F(S-1,T-u)\times N^{T-u}}}{N^T}$
$= \sum_{u \geq need[S]}{\frac{_{u}^{T}C\times F(S-1,T-u)}{N^u}}$

F(N, G) is the result probability.

Note that F(S, T) is not a probability value. The correct probability value should be $\frac{C(S, T)}{S^T}$, not $\frac{C(S, T)}{N^T}$. To define F(S,T) is a trick to get the result probability faster.

Probability and cardinality could be used interchangeably.

When constructing a DP solution, use cardinality to be clearer. After that, divide the cardinality to the total outcome to get the probability function.

Of course, we could also define $F(S,T) = \frac{C(S,T)}{S^T}$, which is the correct probability value. A little bit more machine computations is required.