自动搬运

查看原文

来自洛谷，原作者为

	喵仔牛奶 黄昏再美终要黑夜。

搬运于2025-08-24 23:09:50，当前版本为作者最后更新于2025-03-17 08:12:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Solution

设 $[x^S]F(x)$ 表示 $S$ 的生成子图个数，定义 $[x^{\emptyset}]F(x)=1$。求出 $c_S$ 表示两端都在 $S$ 中的边的个数，可以发现 $[x^S]F(x)=2^{c_S}$。

设 $[x^S]G(x)$ 表示 $S$ 的连通生成子图个数，定义 $[x^{\emptyset}]G(x)=0$。可以发现 $\exp G=F$，即 $G=\ln F$，做一遍 ln 即可求出 $G$。

设 $[x^S]H(x)$ 表示 $S$ 的生成子图连通值之和，可以发现

$$H(x)=\sum_{n\ge 0}\frac{G^n}{n!}\times n!=\sum_{n\ge 0}G^n=\frac{1}{1-G} $$

做一遍求逆即可求出 $H$。

求 ln 和求逆复杂度都是 $\mathcal O(n^22^n)$，故总复杂度也是这个。

Code

直接贺两个板子上去会被卡常，见 https://uoj.ac/submission/743330。

需要把两个写到一起，能够省 $2n$ 次 FWT，就可以通过啦。

#include <bits/stdc++.h>
#define REP(i, l, r) for (int i = (l); i <= (r); ++ i)
#define DEP(i, r, l) for (int i = (r); i >= (l); -- i)
#define fi first
#define se second
#define pb emplace_back
#define mems(x, v) memset((x), (v), sizeof(x))
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
using namespace std;
namespace math { ... }
namespace Milkcat {
	using namespace math;
	typedef long long LL;
	typedef pair<LL, LL> pii;
	const int N = 20, mod = 998244353;
	typedef mint<mod> MI;
	int n, k, x, y; MI f[1 << N], g[1 << N], A[N + 1][1 << N], B[N + 1][1 << N];
	void fwt(MI* f, int n, int o) {
		REP(i, 0, n - 1) REP(j, 0, (1 << n) - 1)
			if (j >> i & 1) f[j] += f[j ^ 1 << i] * o;
	}
	int ppc(int x) { return __builtin_popcount(x); }
	int main() {
		cin >> n >> k;
		REP(i, 1, k) {
			cin >> x >> y, x --, y --;
			f[1 << x | 1 << y] += 1;
		}
		fwt(f, n, 1);
		REP(i, 0, (1 << n) - 1)
			f[i] = qpow((MI)2, f[i].val());
		int m = (1 << n);
		REP(i, 0, m - 1) A[ppc(i)][i] = f[i];
		REP(i, 0, n) fwt(A[i], n, 1);
		REP(i, 1, n) {
			REP(j, 1, i - 1) REP(S, 0, m - 1)
				B[i][S] += B[j][S] * A[i - j][S] * j;
			MI iv = (MI)1 / i;
			REP(S, 0, m - 1) B[i][S] = A[i][S] - B[i][S] * iv;
		}
		REP(i, 0, n) REP(j, 0, m - 1)
			A[i][j] = -B[i][j] + 1, B[i][j] = 0;
		REP(S, 0, m - 1) B[0][S] = A[0][S].inv();
		REP(i, 1, n) REP(j, 1, i) REP(S, 0, m - 1)
			B[i][S] -= A[j][S] * B[i - j][S] * B[0][S];
		fwt(B[n], n, -1);
		cout << B[n][m - 1] << '\n';
		return 0;
	}
}