对每个 \(1\leqslant i\leqslant n\) 求 \(i\) 个点的弱连通有标号有向无环图数目，\(n\leqslant 10^5\)。
首先，根据 exp 的组合意义，即有标号对象组成的集合个数，如果我们求出了不一定弱连通的 DAG 数目的 EGF \(G(x)\)，设弱连通的 DAG 数目的 EGF 为 \(F(x)\)，则 \[ F(x)=\ln(G(x)) \] 显然一张 DAG 一定有至少一个入度为 \(0\) 的点，所以我们尝试枚举度数为 \(0\) 的点的个数，然后我们计算度数为 \(0\) 的点和其它点的连边情况，然后就递归到了子问题，这样你可能会写出以下式子 \[ g_i=\sum\limits_{j=1}^i\binom{i}{j}2^{j(i-j)}g_{i-j} \] 但是写个暴力试一下发现是错的，为什么？因为剩下的点里可能也有入度为 \(0\) 的点，所以会计重。
我们发现，我们实际上不是枚举入度为 \(0\) 的点，而是在钦定入度为 \(0\) 的点，我们设 \(h_{i,j}\) 为\(i\) 个点的图钦定 \(j\) 个入度为 \(0\) 个点的方案数，\(c_{i,j}\) 为恰好 \(j\) 个入度为 \(0\) 的点的方案数，那么有（这个式子都不知道见了多少遍了）： \[ h_{i,j}=\sum\limits_{k=j}^i \binom{k}{j}c_{i,k} \] 由二项式反演： \[ c_{i,j}=\sum\limits_{k=j}^i \binom{k}{j}(-1)^{k-j}h_{i,k} \] 同时类似刚才那个假的式子，我们有 $h_{i,j}=2^{j(i-j)}g_{i-j} $，有 \(g_i=\sum\limits_{j=1}^i c_{i,j}\)。
然后我们把能带入的都带入 \[ \begin{aligned} g_n&=\sum\limits_{i=1}^nc_{n,i}\\ &=\sum\limits_{i=1}^n\sum\limits_{j=i}^n\binom{j}{i}(-1)^{j-i}h_{i,j}\\ &=\sum\limits_{i=1}^n\sum\limits_{j=i}^n\binom{j}{i}(-1)^{j-i}\binom{n}{j}2^{j(n-j)}g_{n-j}\\ &=\sum\limits_{j=1}^n\binom{n}{j}2^{j(n-j)}g_{n-j}\sum\limits_{i=1}^{j}\binom{j}{i}(-1)^{i-j}\\ &=\sum\limits_{j=1}^n\binom{n}{j}2^{j(n-j)}g_{n-j}(0-(-1)^j)\\ &=\sum\limits_{j=1}^n\binom{n}{j}(-1)^{j+1}2^{j(n-j)}g_{n-j} \end{aligned} \]
然后注意到有个 \(j(n-j)\)，我们采用和 Bluestein 一样的套路，把 \(j(n-j)\) 拆成组合数的和。 \[ j(n-j)=\binom{n}{2}-\binom{j}{2}-\binom{n-j}{2} \]
如果记不住可以考虑组合意义：等价于有两堆石子，各有 \(j\) 和 \(n-j\) 个，然后从两堆石子各取一个的方案数等于任取的方案数减去同时在一堆石子里取的方案数。
这里没有用平方式的那个，因为不一定存在 \(2\) 的二次剩余（虽然 AKrry 证明了如果是 NTT 模数都存在）。
这样就是卷积形式了 \[ \begin{aligned} g_n=\sum\limits_{j=1}^n\binom{n}{j}(-1)^{j+1}2^{j(n-j)}g_{n-j}\\ \frac{g_n}{n!2^{\binom{n}{2}}}=\sum\limits_{j=1}^n\frac{(-1)^{j+1}}{2^{\binom{j}{2}}j!}\frac{g^{n-j}}{2^\binom{n-j}{2}(n-j)!} \end{aligned} \] 设 \[ F(x)=\sum\limits_{i=1}^\infty \frac{(-1)^{i+1}}{2^{\binom{i}{2}}i!}x^i\\ G(x)=\sum\limits_{i=0}^\infty \frac{g_i}{2^{\binom{i}{2}}i!}x^i \]
则 \(G(x)=F(x)G(x)+1\)，故 \(G(x)=\frac{1}{1-F(x)}\)。这样就可以求出 \(g\)，然后再做一遍 \(\ln\) 就好了。
代码：
1 |
|