这道题目虽然是放在容斥原理题单里面的,但实际上用的是二项式反演(当然这东西也是由容斥原理推导出来的)
但是啦我已经很满足了,我自己已经推出了大部分的式子了,只是最后不会二项式反演而已
这种没什么思路的题目,我们先从小范围开始想起
我们假设只有一门课,那么我们从\(n-1\)个同学中选出\(k\)个人(\(C_{n-1}^k\)),表示这些人被B神碾压,那么剩下的\(n-1-k\)个人的成绩都严格大于B神。我们假设B神的成绩是\(g\),那么答案就是\(C_{n-1}^kg^{k}(u-g)^{n-1-k}\)(注意要满足B神的排名与被碾压的人数不矛盾)
现在我们来看看有两门课。我们先从第一轮考虑,我们先选出\(r_1-1\)个人(\(C_{n-1}^{r_1-1}\))表示这些人的成绩严格大于B神,那么剩下的\(n-r_1\)个人就是在这门课中成绩没有超过B神的人。那么我们对第二门课做同样的操作,然后我们来判断是否符合条件。我们发现,当一个人在两门课都没被选择的时候,他才会被B神碾压,也就是说,我们设第一门课中选出的\(r_1-1\)个人的集合是\(S_1\),第二门课选出的\(r_2-1\)个人的集合是\(S_2\),那么我们需要满足\(k=n-1-|S_1∪S_2|\)
然后我们推广到三门课,有\(k=n-1-|S_1∪S_2∪S_3|\),然后我们就可以推广到\(m\)门课了
也就是说,先选择\(k\)个人表示这\(k\)个人不在任何一个\(S_i\)里面,而且最后要有\(|∪S_i|=n-1-k\)
我们先选择\(k\)个人,很显然,为\(C_{n-1}^k\)
然后我们来考察满足\(|∪S_i|=n-1-k\)的所有的方案数,这东西就要用到二项式反演了。有关二项式反演
然后我们发现我们整体的结构就已经确认好了。假设我们现在已经有了B神的成绩,分别为\((g_1,g_2,...,g_m)\),那么选出的\(k\)个人的第\(i\)门课的成绩就有\(g_i\)种选择,没被选出来的\(n-1-k\)个人第\(i\)门课的成绩就有\(u_i-g_i\)种选择,我们根据乘法原理乘起来就好了(这其实是非常重要的一个点,感觉很多容斥的题目,或者说计数的题目,当结构不同的时候,贡献是一样的,所以我们只用计算结构的数量就好了,比如这道题目,我们并不关心这\(k\)个人具体是谁,因为只有数量是一样的,贡献就一样)
但是还有个问题,我们不可能枚举每一个\(g\),这个时候就可以看这篇题解
标签:选出,门课,个人,我们,反演,成绩,比较 From: https://www.cnblogs.com/dingxingdi/p/18076006