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)).