二项式反演
定义 fi 表示有将 i 个不同的元素组成的特定结构的方案数,gi 表示从 i 个元素任意选出一些(可以不选)组成特定结构的方案数。
对于知道 fi 或者 gi 中的任意一个就可求解另外一个,其公式如下:
gn=i=0∑n(in)fi
fn=i=0∑n(in)(−1)n−igi
就是容斥,直接感性理解就完了。
思路
题目求的是 gi,考虑把 fi 用 DP 算出来。
定义 fx,i′ 表示节点 x 为根的子树内有,拟定有 i 个满足父子关系的,那么只考虑子树内的情况有:
fx,i+j′←fx,i+j′+p∈son(i)∑fp,k′×fx,j′
最后把 x 的贡献加进去,设 s 是颜色与 x 不同的子树内的节点数量,那么就有:
fx,i′←fx,i′+fx,i−1′×max(s−(j−1),0)
考虑剩余的随便选,也就是 fi=f1,i′×(2n−k)!。
最后把 f 丢给二项式反演就算出了 gi 也就是答案了,时间复杂度为 O(n2)。