主要思路
真你妈毒瘤。
原式子是长这个样子的：
\[ f(n) = \sum_{i = 0}^n \sum_{j = 0}^i \begin{Bmatrix} i \\ j \end{Bmatrix} 2^j (j!) \]
真你妈毒瘤。
原式子是长这个样子的：
\[ f(n) = \sum_{i = 0}^n \sum_{j = 0}^i \begin{Bmatrix} i \\ j \end{Bmatrix} 2^j (j!) \]
我们发现，直接算一个连通块非常的困难。这个时候可以尝试容斥。我们发现至少一个的特别好算：划分至少\(i\)个连通块的答案记为\(g(i)\)。\(g(i)\)比较好算，可以考虑 DFS 枚举出每一个点所在的连通块根，然后把连通情况放入线性基中，如果线性基插入失败，那么说明当前的情况不能被表示出，且该状态符合划分，那么计入小答案\(tot\)，最后对答案的贡献就是：\(2^{tot}\)。
现在考虑如何用\(g(i)\)算恰好\(i\)个连通块的答案\(f(i)\)。考虑搞下容斥系数，使得\(f(i)\)只被计算一次：
\[ \sum_{i = 1}^n \begin{Bmatrix} n \\ i \end{Bmatrix} coefficient(i) = [n = 1] \]
打表出来就是：
\[ coefficient(i) = (-1)^{i – 1} (i – 1)! \]