Qiuly

「TJOI2019」唱、跳、rap 和篮球 容斥+组合数学+DP loj3106
草之前想麻烦了。很显然我们需要容斥一下,设 $f_i$ 表示至少有 $i$ 堆同学讨论 cxk ,那么很显然 $f...
扫描右侧二维码阅读全文
09
2019/09

「TJOI2019」唱、跳、rap 和篮球 容斥+组合数学+DP loj3106

草之前想麻烦了。

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

代码咕咕咕咕到时候补上

最后修改:2019 年 09 月 09 日 08 : 24 PM

发表评论