目录
前面有一些题解还没补啊, 但有人急着看就先发出来啦.
「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_i\sum_{j=0}^i{i\brace j}j!\sum_{k=m}^{2m}\binom{k}{m}\binom{m}{k-m}\binom{n}{j+k}\\ &= \sum_{j=0}^m\sum_{k=m}^{2m}j!\cdot\binom{k}{m}\binom{m}{k-m}\cdot\binom{n}{j+k}\color{red}{\sum_{i=j}^mf_i{i \brace j}}\\ &= \sum_{j=0}^m\sum_{k=m}^{2m}j!\cdot\binom{k}{m}\binom{m}{k-m}\cdot\binom{n}{j+k}\color{red}{\sum_{i=0}^mf_i\frac{1}{j!}\sum_{t=0}^j(-1)^{j-t}\binom{j}{t}t^i}\\ &= \sum_{j=0}^m\sum_{k=m}^{2m}j!\cdot\binom{k}{m}\binom{m}{k-m}\cdot\binom{n}{j+k}\color{red}{\sum_{t=0}^j\frac{(-1)^{j-t}}{j!}\binom{j}{t}\sum_{i=0}^mf_it^i}\\ &= \sum_{j=0}^m\sum_{k=m}^{2m}j!\cdot\color{blue}{\binom{k}{m}\binom{m}{k-m}}\cdot\binom{n}{j+k}\color{red}{\sum_{t=0}^j\frac{F(t)}{t!}\cdot\frac{(-1)^{j-t}}{(j-t)!}}\\ &= \sum_{j=0}^m\sum_{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(m\log m)\).
标签：Set,cdot,sum,Solution,color,寒假,2m,binom,red From： https://www.cnblogs.com/rainybunny/p/17049095.html