题意:给定n个环再给定k个人 求把k个人放到n个环上每个环至少一个人的方案数
直接暴力dp 65分 那么考虑正解
设A(x) 为当这个环大小为size时的生成函数 那么x^i前面的系数A(x)=\sum\limits_{i=1}^{size}\binom{size}{i}然后直接合并即可 但是暴力合并复杂度是不对的 注意到合并大小为sa,sb循环的时候复杂度是(sa+sb)log(n)那么这个和哈夫曼编码的过程其实相似我们使用哈夫曼编码的顺序合并每次将最小的两个size合并一下 然后因为多项式次数不会超过n所以复杂度是n*log(2)^{2}

 


elijahqi

退役了 现在在商院 偶尔打CF,有时有ACM regional也去玩一下

发表评论