[洛谷P4841]城市规划

题目大意：求$n$个点的带标号的无向连通图的个数

题解：令$F(x)$为带标号无向连通图个数生成函数，$G(x)$为带标号无向图个数生成函数

那么$G(x) = \sum_{i=0}^{\infty} \dfrac{2^{i(i-1)/2}}{i!} x^i$

枚举连通块个数可得$G(x)=\sum_{i=0}^{\infty}\dfrac{F^i(x)}{i!}$
$$
f(x)=f(x_0)+\dfrac{f'(x_0)(x-x_0)}{1!}+\dfrac{f''(x_0)(x-x_0)^2}{2!}+\cdots+\dfrac{f^{(n)}(x_0)(x-x_0)^n}{n!}\\
f(x)=e^x, x_0=0\\
e^x=\sum\limits_{i=0}^{\infty}\dfrac{x^i}{i!}
$$

由泰勒展开得$G(x)=e^{F(x)}$

所以$F(x) = \ln G(x)$

$$
F(x)=\ln G(x)\\
F'(x)=\dfrac{G'(x)}{G(x)}\\
F(x)=\int\dfrac{G'(x)}{G(x)}\mathrm{dx}
$$

答案是$[x^n]F(x) \times n!$

卡点：无

C++ Code：

#include <cstdio>

#include <algorithm>

#define maxn 262144 + 10

const int mod = 1004535809, G = 3;

int n;

int g[maxn], f[maxn], fac[maxn], inv[maxn];

inline int pw(int base, long long p) {

	p %= mod - 1, base %= mod;

	int res = 1;

	for (; p; p >>= 1, base = 1ll * base * base % mod) if (p & 1) res = 1ll * res * base % mod;

	return res;

}

inline int INV(int x) {

	return pw(x, mod - 2);

}

namespace Polynomial {

	int lim, ilim, s, rev[maxn];

	int C[maxn], Wn[maxn];

	inline void init(int n) {

		s = -1, lim = 1; while (lim < n) lim <<= 1, s++;

		ilim = ::INV(lim);

		for (int i = 1; i < lim; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << s);

		int tmp = pw(G, (mod - 1) / lim);

		Wn[0] = 1; for (int i = 1; i <= lim; i++) Wn[i] = 1ll * Wn[i - 1] * tmp % mod;

	}

	inline void up(int &a, int b) {if ((a += b) >= mod) a -= mod;}

	inline void NTT(int *A, int op) {

		for (int i = 0; i < lim; i++) if (i < rev[i]) std::swap(A[i], A[rev[i]]);

		for (int mid = 1; mid < lim; mid <<= 1) {

			int t = lim / mid >> 1;

			for (int i = 0; i < lim; i += (mid << 1)) {

				for (int j = 0; j < mid; j++) {

					int W = op ? Wn[t * j] : Wn[lim - t * j];

					int X = A[i + j], Y = 1ll * W * A[i + j + mid] % mod;

					up(A[i + j], Y), up(A[i + j + mid] = X, mod - Y);

				}

			}

		}

		if (!op) for (int i = 0; i < lim; i++) A[i] = 1ll * A[i] * ilim % mod;

	}

	void INV(int *A, int *B, int n) {

		if (n == 1) {B[0] = ::INV(A[0]); return ;}

		INV(A, B, n + 1 >> 1), init(n << 1);

		for (int i = 0; i < n; i++) C[i] = A[i];

		for (int i = n; i < lim; i++) C[i] = B[i] = 0;

		NTT(B, 1), NTT(C, 1);

		for (int i = 0; i < lim; i++) B[i] = (2 + mod - 1ll * B[i] * C[i] % mod) * B[i] % mod;

		NTT(B, 0);

		for (int i = n; i < lim; i++) B[i] = 0;

	}

	inline void DER(int *A, int *B, int n) {

		B[n] = 0; for (int i = 1; i < n; i++) B[i - 1] = 1ll * A[i] * i % mod;

	}

	inline void INT(int *A, int *B, int n) {

		B[0] = 0; for (int i = 1; i < n; i++) B[i] = 1ll * A[i - 1] * ::INV(i) % mod;

	}

	int D[maxn];

	inline void LN(int *A, int *B, int len) {

		DER(A, B, len);

		INV(A, D, len);

		init(n << 1);

		NTT(B, 1), NTT(D, 1);

		for (int i = 0; i < lim; i++) D[i] = 1ll * B[i] * D[i] % mod;

		NTT(D, 0);

		INT(D, B, len);

		for (int i = len; i < lim; i++) B[i] = 0;

	}

}

int main() {

	scanf("%d", &n); n++;

	fac[0] = fac[1] = inv[0] = inv[1] = 1;

	for (int i = 2; i < n; i++) {

		fac[i] = 1ll * fac[i - 1] * i % mod;

		inv[i] = 1ll * inv[mod % i] * (mod - mod / i) % mod;

	}

	for (int i = 2; i < n; i++) inv[i] = 1ll * inv[i - 1] * inv[i] % mod;

	for (int i = 0; i < n; i++) g[i] = 1ll * pw(2, 1ll * i * (i - 1) >> 1ll) * inv[i] % mod;

	Polynomial::LN(g, f, n);

	printf("%lld\n", 1ll * f[n - 1] * fac[n - 1] % mod);

	return 0;

}

巴特西

[洛谷P4841]城市规划

最新文章

热门文章