Let’s consider that at last we have \(x\) different prizes of lottery:\(\{c_1,c_2,...,c_x\}\).Let \(p(i)\) be \(\frac{W_i}{\sum_{i=1}^N W_i}\) and \(P(\{c_1,c_2...,c_x\})\) be the probabily that after \(K\) draws we get excatly \(x\) different prizes of lottery: \(\{c_1,c_2,...,c_x\}\).

Well, Let \(P=\sum_{i=1}^x p(c_i)\), thus ,\(P^K\) will be the value below:

\[\sum P(\{d_1,d_2,...,d_y\})\times [\{d_1,d_2,...,d_y\} \subset \{c_1,c_2,...,c_x\}]\]

By inclusion-exclusion principle, Let \(f(x)=\sum P(\{d_1,d_2,...,d_x\})\) and the answer will be:

\[\sum_{i=1}^{M}(-1)^{M-i}\times \dbinom{N-i}{M-i}\times f(i)\]

We just need to calculate \(f(1\sim M)\).

Now comes a dynamic programming ：Let \(dp(i,j,k)\) be \(\sum P(\{d_1,d_2,...,d_j\})^k \times [\{d_1,d_2,...,d_j\}\subset\{1,2,...,i\}]\)。And \(f(i)\) will be equal to \(dp(N,i,K)\).

To calculate \(dp(i,j,k)\) ,there are two cases:

• We don’t choose \(i\),so \(dp(i-1,j,k)\rightarrow dp(i,j,k)\).

• We choose \(i\), by binomial theorem we can get:

\[\sum_{x=0}^{k}\dbinom{k}{x}\times dp(i-1,j-1,x)\times p(i)^{k-x}\rightarrow dp(i,j,k)\]

The time of calculating all \(dp(i,j,k)\) is \(O(NMK^2)\).

implementation：https://atcoder.jp/contests/abc243/submissions/30067934