Solution - P3223 [HNOI2012] 排队

P3223 [HNOI2012] 排队

idea:

比较简单的排列组合，比较不恶心但还是恶心的高精度。

解决方案：

按照套路，容斥一下，先不考虑老师。此时老师与男同学等价。答案为：

$$C_{n+2+1}^{m}\cdot (n+2)!\cdot m! = \frac{(n+3)!}{(n+3-m)!}\cdot (n+2)!$$

这一部分可以 $O((m+n)\cdot k)$ 求出。 $k$ 为高精乘单精复杂度。

下面把两个老师粘在一起。答案为：

$$C_{n+1+1}^{m}\cdot C_{n+1}^1\cdot n!\cdot m!\cdot 2 = \frac{(n+2)!}{(n+2-m)!}\cdot (n+1)!\cdot 2$$

这一部分复杂度仍然是 $O((m+n)\cdot k)$ 。

总复杂度 $O((m+n)\cdot k)$ 。只需要高精乘以单精以及高精减两个操作。