显然只需对于 \(i\in [1,n]\) 求出将图划分为 \(i\) 个独立集的方案数。
若令 \(f_S=[\text{S 为独立集}]\)，\(F\) 为 \(f\) 的集合幂级数，则此值为 \([x^U]\frac{F^i}{i!}\)。
此时只需对带占位多项式的集合幂级数进行 \(FMT\)，而后可以暴力 \(O(n^2)\) 多项式快速幂，此时已经可以做到 \(O(2^n\times n^3)\) 的复杂度。
注意到 \(f_S\) 的初值只有 \(0,1\) 两种，所以我们猜测 \(FMT(F)\) 后本质不同的多项式是少的，对其进行记忆化即可。复杂度 \(O(D\times n^3)\)，其中 \(D\) 为等价类个数。
经检验，在随机图上 \(D \approx 1\times 10^4\)，而稀疏图以及稠密图理应更加优秀。
有没有人来叉一下，有的话就是 hez 造的数据太弱了。