看了某神仙博客学了一手,基本的思路就是容斥入度为0的点。
n^2做法。
F(n)=sigema i (-1)^(i-1)✖ C(n,i)✖ F(i)✖ 2^(j*(i-j))
nlogn做法
对上述式子进行优化
(引用了yyb大佬博客的图片,非常感谢,侵删)
(留下了不会用Latex的眼泪)
上述式子xjb做的话可以分治NTT,但那样做很蠢,没必要。
这个式子还挺经典的,是一个F[n]=sigema F[i]G[n-i]的形式。
此时存在等式F(x)=F(X)G(X)+1,因此直接求逆即可。
如果还要求满足弱联通,或许可以直接ln一下?