JLOI2016成绩比较

$\color{deeppink}link$

令 $f_{i}$ 表示至少有 $i$ 人被吊打的方案数。

则有

$f_i=\binom{n-1}{i}\prod_{j=1}^m \binom{n-i-1}{r_j-1}\sum_{k=1}^{u_j}k^{n-r_j}(u_j-k)^{r_j-1}$

然后考虑化简一下最后的和式

$\sum_{k=1}^{u_j}k^{n-r_j}(u_j-k)^{r_j-1}\\ =\sum_{k=1}^{u_j}k^{n-r_j}\sum_{l=0}^{r_j-1}\binom{r_j-1}{l}u_j^{r_j-1-l}(-k)^{l}\\ =\sum_{l=0}^{r_j-1}(-1)^l\binom{r_j-1}{l}u_j^{r_j-1-l}\sum_{k=1}^{u_j}k^{n-r_j+l}$

然后用拉差即可，最后答案用二项式反演即是

$\sum_{i=k}(-1)^{i-k}\binom{i}{k}f_i$