闲话9.5
今天摆了。
上午写了写期望，下午听 xzt 讲课，晚上摆烂，一天好规律啊🥰🥰🥰
明天就是那个閷榌模拟赛了，我先爆蛋为敬，哈哈😅😅😅
省一生们今天也该都回来了，我他妈明天必定逃掉跑操，閷榌跑操有个吊毛用啊真的是😓😓😓
妈的 jimmy 今天下午还看我们博客是吧😓😓😓，等他看到我和 tzx 的博客看他是什么表情🤣
来点难绷
某无良记者
/yiw
没有攻击某个人，只是在讨论我的做题状况
图片来自 haosen
推歌：魔王 -sasakure.UK/TJ.hangneil
我 X 我 自 己
当初打 Arcaea 4.0 的时候一解这首歌就被曲师震惊到了，竟然是飒飒酷热和天津红牛。后面打歌过程也挺愉悦的其实（仅享受音乐来说）
总的来说也符合我对这个曲师作曲曲风的想象吧，之前听 Apollo 的时候就被震惊到了，这次再被震惊一次也不为过。
P3270
首先我们发现恰好 \(k\) 这个条件不太好搞，我们就可以用二项式反演来把它搞掉。
我们设 \(g_i\) 为至少 \(i\) 个人被碾压的方案数，我们就可以得到最终的答案为：
\[ans=\sum\limits_{i=k}^{n-1}\dbinom{i}{k}(-1)^{i-k}g_i
\]
我们现在就考虑如何求出 \(g_i\)。我们对于每一科分开考虑，先选出 \(i\) 个人被碾压，然后再从剩下的 \(n-1-i\) 人中选出分数比他低的剩下 \(n-r_i-i\) 个人。最后再枚举他的分数，将两拨人分开放即可。
因此我们最终出来的式子是：
\[g_i=\dbinom{n-1}{i}\prod_{j=1}^m\dbinom{n-i-1}{n-r_j-i}\sum\limits_{k=1}^{u_j} k^{n-r_j}(u_j-k)^{r_j-1}
\]
然后我们发现最后的 \(\sum\) 很难求，因为 \(u\) 的范围太大。我们尝试化一下式子。
\[\begin{aligned}
g_i&=\dbinom{n-1}{i}\prod_{j=1}^m\dbinom{n-i-1}{n-r_j-i}\sum\limits_{k=1}^{u_j} k^{n-r_j}(u_j-k)^{r_j-1}\\
&=\dbinom{n-1}{i}\prod_{j=1}^m\dbinom{n-i-1}{n-r_j-i}\sum\limits_{k=1}^{u_j}k^{n-r_j}\sum\limits_{l=0}^{r_j-1}\dbinom{r_j-1}{l}(-k)^l u_j^{r_j-1-l}\\
&=\dbinom{n-1}{i}\prod_{j=1}^m\dbinom{n-i-1}{n-r_j-i}\sum\limits_{l=0}^{r_j-1}\dbinom{r_j-1}{l}u_j^{r_j-1-l}(-1)^l\sum\limits_{k=1}^{u_j}k^{n-r_j+l}
\end{aligned}
\]
我们发现最后的 \(\sum\limits_{k=1}^{u_j}k^{n-r_j+l}\) 是可以直接 \(O(n)\) 插出来的，因此就可以解决了。
时间复杂度 \(O(n^3)\)
今日图图：
