前传，一年之期已到！来看一看 gf 去凑容斥系数！
经典例题：20210620省队互测-qwaszx T2，jiangly 的排列数数题，P7275 计树
一个组合对象由若干元素组成，但是元素直接可能可以合并，不能任意拼接。先假设可以任意拼接，然后对系数分配适当的容斥系数（此时一个方案的贡献要乘上所有元素的容斥系数的乘积）使得每个大小的元素被任意拼接合并出来的系数乘积之和恰好是我们想要它贡献的。
duye 如是说：我们无法直接计算满足某种条件的方案数，但可以计算另一些与原条件相关的条件的方案数，然后对每种情况赋予一个容斥系数，使得满足原条件的每种情况对应的容斥系数之和恰为 \(1\)，不满足的情况对应的容斥系数之和恰为 \(0\).
以 20210620省队互测-qwaszx T2 为例，如果可以任意拼接，先不考虑段之间的编号分配，仅考虑段内部是上升还是下降带来的方案数，那就是 \([x^1]G(x)=1\)，\([x^i]G(x)=2,i\geq 2\)．然后 \(\sum_{i\geq 0}i!G^i(x)\) 就是答案的 ogf．但是段和段之间可能可以合并，需要给 \(G(x)\) 的每一项系数乘一个适当的容斥系数，使得它任意拼接得到的是 \(x+x^2+\cdots+x^{m-1}\)，假设容斥系数的 ogf 是 \(F(x)\)，那么这里就有 \(\frac{1}{1-F(x)}-1=\frac{x-x^m}{1-x}\)，解得 \(F(x)=\frac{x-x^m}{1-x^m}\)，和 \(G(x)\) 点乘得到 \(H(x)\)，那么 \(\sum_{i\geq 0}i!H^i(x)\) 就是答案。
最开始的三个例子都是形式幂级数的 SEQ 构造。对于 DAG 计数问题的 \((-1)^{|S|+1}\) 容斥系数也可以用类似的思路推导。
这里采用集合幂级数，乘法定义为不交并卷积（子集卷积），乘法逆同理。每次将入度为 \(0\) 的所有点在图中删去，并且记做一个新的多重集。这样就能把 DAG 转化成若干多重集。比较简单的想法是 \(f_S=\sum_{T\subseteq S}f_T2^{|T|(|S|-|T|)}\)，但是会有计重情况，依然考虑去分配容斥系数使得不会计重，用集合幂级数列出来就是 \(\frac{1}{1-F(x)}=1+x+x^2+x^3\cdots\)（这里集合幂级数的 Sequence 构造依然是 \(\frac{1}{1-F(x)}=1+F(x)+F^2(x)+F^3(x)\cdots\)）。那么 \(F(x)=\frac{x+x^2+\cdots}{1+x+x^2+\cdots}\)，手动集合幂级数求逆（分母乘到后面之后提取系数）可以解得 \([x^S]F(x)=(-1)^{|S|+1}\)．