【题解】「TJOI2019」唱、跳、rap 和篮球 容斥+组合数学+DP loj3106 —Qiuly

草之前想麻烦了。

很显然我们需要容斥一下，设 $f _ i$ 表示至少有 $i$ 堆同学讨论 cxk ，那么很显然 $f _ i={n\choose n-3i}$ 。接着设 $g _ i$ 表示至少 $i$ 堆同学讨论 cxk 的情况下剩下的同学的排列方案数，于是我们的最终答案为：
$$
ans=\sum _ {i=0}^{\min(\lfloor\frac{n}{4}\rfloor,a,b,c,d)} (-1)^{i}{n\choose n-3i}g _ i
$$
现在我们未解决的问题就是：怎么求 $g _ i$ ?

很容易的得到式子：
$$
\begin{aligned}
g _ i&=\sum _ {t _ 1=0}^{a-i}\sum _ {t _ 2=0}^{b-i}\sum _ {t _ 3=0}^{c-i}\sum _ {t _ 4=0}^{d-i}[\sum\limits _ {i=1}^{4}t _ i=n-4i] \frac{(n-4i)!}{t _ 1!t _ 2!t _ 3!t _ 4!}\\
&=(n-4i)!\sum _ {t _ 1\leq a-i,t _ 2\leq b-i,t _ 3\leq c-i,t _ 4\leq d-i}[\sum\limits _ {i=1}^{4}t _ i=n-4i] \frac{1}{t _ 1!t _ 2!t _ 3!t _ 4!}\\
\end{aligned}
$$
然后就很简单，直接 $O(n^3)$ 做一下就好了 (跑不满)。

代码咕咕咕咕到时候补上