Solution Set - 寒假睡眠记录

管理员

  前面有一些题解还没补啊, 但有人急着看就先发出来啦.

「2018 集训队互测」「LOJ #2504」小 H 爱染色

  Link & Submission.


  Tags:「A.数学-多项式」「A.数学-数学推导」「A.数学-Stirling 数/反演」

  破题的关键在于对 (F(A))(A^i) 的处理. 这个 (A) 可以理解作前缀白球数量, 而为了免于枚举 "前缀", 我们可以把 "前缀" 理解作 "(A^i) 对应的对象被定序在两次染色对应的对象之前" 这样的组合情景. "定序" 自然只能对小球定序, 那么我们思路就是把前后两项分别转化为 "选一些小球" 的方案数, 然后将选出来的小球一起放入长度为 (n) 的可用序列, 就能求出答案.

  对于 (A^i), Stirling 反演恰好提供了一个很好的转化: 枚举 "在 (A) 个球中任选有序可重复的 (i) 个球" 时, 最终被选过的球数. 对于两次染色, 直接枚举最终被染黑的求数就能完成转化. 枚举多项式的次数 (i), (A^i) 中被选过的球数 (j), 被染黑的球数 (k), 可以表达出答案:

[begin{aligned} textit{ans} &= sum_{i=0}^mf_isum_{j=0}^i{ibrace j}j!sum_{k=m}^{2m}binom{k}{m}binom{m}{k-m}binom{n}{j+k}\ &= sum_{j=0}^msum_{k=m}^{2m}j!cdotbinom{k}{m}binom{m}{k-m}cdotbinom{n}{j+k}color{red}{sum_{i=j}^mf_i{i brace j}}\ &= sum_{j=0}^msum_{k=m}^{2m}j!cdotbinom{k}{m}binom{m}{k-m}cdotbinom{n}{j+k}color{red}{sum_{i=0}^mf_ifrac{1}{j!}sum_{t=0}^j(-1)^{j-t}binom{j}{t}t^i}\ &= sum_{j=0}^msum_{k=m}^{2m}j!cdotbinom{k}{m}binom{m}{k-m}cdotbinom{n}{j+k}color{red}{sum_{t=0}^jfrac{(-1)^{j-t}}{j!}binom{j}{t}sum_{i=0}^mf_it^i}\ &= sum_{j=0}^msum_{k=m}^{2m}j!cdotcolor{blue}{binom{k}{m}binom{m}{k-m}}cdotbinom{n}{j+k}color{red}{sum_{t=0}^jfrac{F(t)}{t!}cdotfrac{(-1)^{j-t}}{(j-t)!}}\ &= sum_{j=0}^msum_{k=m}^{2m}j!{color{red}{f(j)}}cdot{color{blue}{g(k)}}binom{n}{color{green}{j+k}}\ &= sum_{{color{green}s}=m}^{3m}binom{n}{s}sum_{j+k=s}j!f(j)g(k). end{aligned} ]

  化简比较初等, 就不解释了. 算 (f) 和答案各需要一次多项式乘法. 复杂度 (mathcal O(mlog m)).