题目链接
不考虑弱联通的限制，令(g_i) 表示(i) 个带标号点的(DAG) 个数。
(DAG) 的一大特点是必然存在入度为(0) 的点。
令(c_{i,j}) 表示(i) 个点恰好有(j) 个入度为(0) 的(DAG) 个数，那么有
[g_i=sum_{j=1}^ic_{i,j}
]
直接计算(c) 十分困难，考虑二项式反演，令(h_{i,j}) 表示(i) 个点钦定了(j) 个入度为(0) 的点剩下的随便的(DAG) 计数，那么显然有
[h_{i,j}=sum_{k=j}^iinom kjc_{i,k}
]
反演一下可得
[c_{i,j}=sum_{k=j}^iinom kj(-1)^{k-j}h_{i,k}
]
而(h) 的计算是较为容易的，我们有
[h_{i,j}=inom ij2^{j(i-j)}g_{i-j}
]
于是就得到
[g_i=sum_{j=1}^isum_{k=j}^iinom kj(-1)^{k-j}inom ik2^{k(i-k)}g_{i-k}\
=sum_{k=1}^iinom ik2^{k(i-k)}g_{i-k}sum_{j=1}^kinom kj(-1)^{k-j}\
=sum_{k=1}^iinom ik2^{k(i-k)}g_{i-k}(0-(-1)^k)\
=sum_{k=1}^iinom ik(-1)^{k+1}2^{k(i-k)}g_{i-k}\
Rightarrow frac {g_i}{i!}=sum_{k=1}^ifrac{(-1)^{k+1}}{k!}2^{k(i-k)}frac {g_{i-k}}{(i-k)!}
]
这里有一个神仙技巧
[k(i-k)=inom i2-inom k2-inom{i-k}2
]
组合意义的话就是有两个集合，一个集合中有(k) 个元素，另一个有(i-k) 个元素，从中各选取一个的方案数等于总方案数减去不合法的。
于是就有
[frac {g_i}{2^{inom i2}i!}=sum_{k=1}^ifrac {(-1)^{k+1}}{2^{inom k2}k!}cdotfrac {g_{i-k}}{2^{inom {i-k}2}(i-k)!}(i>0)
]
令
[F(x)=sum_{i=1}^{+infty}frac {(-1)^{i+1}}{2^{inom i2}i!}x^i\
G(x)=sum_{i=0}^{+infty}frac {g_i}{2^{inom i2}i!}x^i
]
于是
[G(x)=F(x)G(x)+1
]
(+1) 是因为有(g_0=1)
解得
[G(x)=frac 1{1-F(x)}
]
求出(g_i) 之后，其(EGF) 的(ln) 就是我们要求的答案了。