Description：

对于 $m\in[0,M]$ ，求出在有 $n$ 个苹果 $m$ 个梨时选出 $k$ 个水果恰好有质数个苹果的方案数，苹果和梨各不相同。

$1\leqslant n\leqslant10^5$

Solution：

先列式子： $$ ans[m]=\frac{\begin{align}\sum_{i=1}^k[i\ is\ prime]\times C_n^i\times C_m^{k-i}\end{align}}{C_{n+m}^k} $$ 考虑怎么把它推成卷积的形式，先把式子中只与 $i$ 有关的拿出来，即： $$ \sum_{i=1}^k[i\ is\ prime]C_n^i\frac{m!}{(k-i)!}\times\frac{1}{(m-k+i)!} $$

设 $a[i]=[i\ is\ prime]\times C^i_n\times\frac {M!}{(k-i)!},b[i]=\frac{1}{(-i)!}$

那么： $$ ans[m]=\sum_{i=0}^ka[i]\times b[k-m-i] $$ 令 $C=A\times B$ ，那么 $ans[m]=C[k-m]$ ，可以用 $NTT$ 求解。

Code：

懒得写代码了