很可能啥都没有 别点 别看
杂题？
给出一个 \(n\) 个顶点的无向完全图，你需要给图上的每条边染上红色或蓝色。
一个顶点的集合 \(S\) 被称作是红色连接的，如果对于 \(S\) 中每对顶点 \((v_1,v_2)\)，都存在只通过红边和 \(S\) 中顶点的路径。相仿地，一个顶点的集合 \(S\) 被称作是蓝色连接的，如果对于 \(S\) 中每对顶点 \((v_1,v_2)\)，都存在只通过蓝边和 \(S\) 中顶点的路径。
你需要以如下方式对图进行染色：
- 至少有一条红边，至少有一条蓝边。
- 对于每个大小不小于 \(2\) 的顶点集 \(S\)（也即 \(|S|\geqslant 2\)），\(S\) 或者是红色连接的，或者是蓝色连接的，但不能同时是红色和蓝色连接的。
计数染色方法，对 \(998244353\) 取模。
\(n\le 10^5\)。
foreverlasting 老师说的好啊，由于红蓝两色等价，我们对 \(n\) 要算的一定是 \(f_n\)，使得 \(f_n\) 乘以二后加一些修正就是答案。我们知道不含边一定合法，所以考虑这修正就是减去全涂一种颜色的情况。所以首先猜测答案就是 \(2f_n - 2\)，根据样例可知 \(f_3 = 4, f_4 = 26\)。扔到 oeis 里我们发现了 A311，你计算一下会发现这就是 \(f\)。
所以为啥？
转化一下题意。我们设蓝色边和所有点组成了图 \(G\)，并钦定 \(G\) 是联通的。记 \(\overline G\) 是 \(G\) 的补图。我们知道，题设的要求就是对 \(\forall |H| \ge 2\) 是 \(G\) 的点导出子图有 \(H\) 和 \(\overline H\) 不同时联通，称这样的 \(G\) 是好的图。我们知道，对 \(|G| = n\) 的图 \(G\) 作好图能得到 \(f_n\)，考虑如何计算。
我们不用考虑对应的点集在 \(\overline G\) 中不连通的 \(H\)，这部分平凡。然后我们只需要考虑每个 \(\overline G\) 中的联通块，如果这些联通块对应的点集都组成了好的图，则 \(G\) 就是好的图。这是有标号组合的形式，我们记好图的有标号类为 \(\mathcal A\)，可以知道
\[\mathcal A = \text{SET}_{\ge 2} (\mathcal A) + \mathcal Z \]翻译就是
\[A(z) = \exp A(z) - A(z) - 1 + z \]查 oeis 可以发现 A311 的 egf 是 exp A(x) = 2*A(x) - x + 1，这两个形式是相符的。
到了这一步，下面的推导就是所谓的“标准处理方法”了。
一种直接的做法是采用牛顿迭代，我们设辅助函数 \(F(x) = \exp x - 2x - 1 + z\)，这样求导能得到 \(F'(x) = \exp x - 2\)，直接作即可。总时间复杂度 \(O(n\log n)\)。Submission.
另一种易于发现的方式是拉格朗日反演。这形式就是 \(2A(z) + 1 - \exp A(z) = z\)，我们很容易发现 \(A^{\langle -1 \rangle}(x) = 2x + 1 - \exp x\)，显然这个的最低次项在 \(x^1\) 处取得。听说有人不会推这个咋算？
\[\begin{aligned} \left[x^n /n!\right] A(x) = n![x^n]A(x) = n! \frac{1}{n} [x^{n - 1}] \left(\frac{1}{A^{\langle -1 \rangle}(x)}\right)^n = \left[\frac{x^{n - 1}}{(n - 1)!}\right] \left(\frac{A^{\langle -1 \rangle}(x)}{x}\right)^{- n} \end{aligned}\]这个推导也可以告诉我们拉反在 egf 上的应用形式。不如先拆占位元推的简单
Submission.
当然总起来看，在这题所需的信息上还是牛顿迭代法更高效，因为这做法可以一次算出前 \(n\) 项结果。
另一些拉格朗日反演易于处理的信息可以看这篇博客的第一题。
所以原题为什么要用 \(O(n\sqrt{n\log n})\) 的算法作 std 呢？
标签：right,frac,闲话,31,overline,23.3,exp,顶点,mathcal From： https://www.cnblogs.com/joke3579/p/chitchat230331.html