草之前想麻烦了。

很显然我们需要容斥一下,设 $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)$ 做一下就好了 (跑不满)。

代码咕咕咕咕到时候补上

分类: 文章

Qiuly

QAQ

4 条评论

smy · 2019年10月18日 9:21 下午

3 方太暴力了吧…

wwlw · 2019年10月5日 9:49 下午

%%%

boshi · 2019年9月18日 3:05 下午

公式挂了。请在公式中所有的下划线的前后添加空格。

    Remmina · 2019年9月18日 11:53 下午

    虽然一开始在我电脑上显示都一切正常,但我还是帮忙把所有下划线都用空格隔开了
    (如果原作者觉得这样改不好可以通过恢复历史版本撤销修改 QvQ)

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注