题目大意

　　求出\(n\)个点的简单（无重边无自环）有标号无向连通图数目。\(n\leq 130000\)。

题解

　　题意非常简单，但做起来很难。这是道生成函数经典题，博主当做例题学习用的。博主看到题解后感到非常惊讶：生成函数还能这么玩！

　　步入正题。首先我们要定义生成函数\(F(x)=\sum\limits_{i\geq 0}f_i\dfrac{x^i}{i!}\)，其中\(f_i\)表示\(i\)个点无向连通图数目。

　　定义生成函数\(G(x)=\sum\limits_{i\geq 0}\dfrac{F^i(x)}{i!}\)。观察发现，\(G\)的第\(i\)项系数表示表示的是\(i\)个连通块构成的若干个结点的图的方案数，\(F(x)\)用\(\text{EFG}\)是因为会牵扯到组合数选择要除掉各个对应的阶乘，\(G(x)\)除掉\(i!\)的阶乘是因为\(i\)组中会重复。不难发现：\(G(x)\)表示的是若干结点的无向图总数！

　　根据泰勒展开有：

\[G(x)=e^{F(x)}
\]

　　所以我们有：

\[F(x)=\ln G(x)
\]

　　多项式求\(\ln\)即可。

　　复杂度：\(\text{O}(n\log n)\)。

　　归纳上面的思路：利用任意个点连通图的数目与任意个点图的数目列等式，然后反解连通图的数目，从而得到答案

代码

#include <bits/stdc++.h>

using namespace std;

const int maxn = 130000 + 5;

const int P = 1004535809, g = 3;

int inc(int a, int b) { return (a += b) >= P ? a-P : a; }

int qpow(int a, int b) {

	int res = 1;

	for (int i = a; b; i = 1ll*i*i%P, b >>= 1)

		if (b & 1) res = 1ll*res*i%P;

	return res;

}

int W[maxn << 3], inv[maxn << 2], fac[maxn << 2], ifac[maxn << 2];

void prework(int n) {

	for (int i = 1; i < n; i <<= 1) {

		W[i] = 1;

		for (int j = 1, Wn = qpow(g, (P-1)/i>>1); j < i; j++) W[i+j] = 1ll*W[i+j-1]*Wn%P;

	}

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

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

	for (int i = 1; i < n; i++) fac[i] = 1ll*fac[i-1]*i%P, ifac[i] = 1ll*ifac[i-1]*inv[i]%P;

}

void ntt(int *a, int n, int opt) {

	static int rev[maxn << 2];

	for (int i = 1; i < n; i++)

		if ((rev[i] = rev[i>>1]>>1|(i&1?n>>1:0)) > i) swap(a[i], a[rev[i]]);

	for (int q = 1; q < n; q <<= 1)

		for (int p = 0; p < n; p += q << 1)

			for (int i = 0, t; i < q; i++)

				t = 1ll*W[q+i]*a[p+q+i]%P, a[p+q+i] = inc(a[p+i], P-t), a[p+i] = inc(a[p+i], t);

	if (~opt) return;

	for (int i = 0; i < n; i++) a[i] = 1ll*a[i]*inv[n]%P;

	reverse(a+1, a+n);

}

struct poly {

	vector<int> A;

	int len;

	poly(int a0 = 0) : len(1) { A.push_back(a0); }

	int &operator [] (int i) { return A[i]; }

	void write() {

		for (int i = 0; i < len; i++) printf("%d ", A[i]);

		putchar('\n');

	}

	void load(int *from, int n) {

		A.resize(len = n);

		memcpy(&A[0], from, sizeof(int) * len);

	}

	void cpyto(int *to, int n) {

		memcpy(to, &A[0], sizeof(int) * min(len, n));

	}

	void resize(int n = 0) {

		if (!n) { while (len > 1 && !A[len - 1]) len--; A.resize(len); } else A.resize(len = n, 0);

	}

} F, G;

poly poly_inv(poly A) {

	poly B = poly(qpow(A[0], P-2));

	for (int len = 1; len < A.len; len <<= 1) {

		static int x[maxn << 2], y[maxn << 2];

		for (int i = 0; i < len << 2; i++) x[i] = y[i] = 0;

		A.cpyto(x, len << 1), B.cpyto(y, len);

		ntt(x, len << 2, 1), ntt(y, len << 2, 1);

		for (int i = 0; i < len << 2; i++) x[i] = inc(y[i], inc(y[i], P-1ll*x[i]*y[i]%P*y[i]%P));

		ntt(x, len << 2, -1);

		B.load(x, len << 1);

	}

	return B.resize(A.len), B;

}

poly operator + (poly A, poly B) {

	if (A.len < B.len) A.resize(B.len);

	for (int i = 0; i < B.len; i++) A[i] = inc(A[i], B[i]);

	return A.resize(), A;

}

poly operator - (poly A, poly B) {

	if (A.len < B.len) A.resize(B.len);

	for (int i = 0; i < B.len; i++) A[i] = inc(A[i], P-B[i]);

	return A.resize(), A;

}

int getsize(int n) { int N = 1; while (N < n) N <<= 1; return N; }

poly operator * (poly A, poly B) {

	static int x[maxn << 2], y[maxn << 2];

	int len = getsize(A.len + B.len - 1);

	for (int i = 0; i < len; i++) x[i] = y[i] = 0;

	A.cpyto(x, A.len), B.cpyto(y, B.len);

	ntt(x, len, 1), ntt(y, len, 1);

	for (int i = 0; i < len; i++) x[i] = 1ll*x[i]*y[i]%P;

	ntt(x, len, -1);

	return A.load(x, A.len + B.len - 1), A.resize(), A;

}

poly poly_deri(poly A) {

	for (int i = 0; i < A.len - 1; i++) A[i] = 1ll*A[i+1]*(i+1)%P;

	return A[A.len - 1] = 0, A.resize(), A;

}

poly poly_int(poly A) {

	for (int i = A.len - 1; i; i--) A[i] = 1ll*A[i-1]*inv[i]%P;

	return A[0] = 0, A;

}

poly poly_ln(poly A) {

	poly B = poly_deri(A) * poly_inv(A);

	return B.resize(A.len), poly_int(B);

}

int n;

int main() {

	scanf("%d", &n); prework((n+1)<<2);

	G.resize(n+1);

	for (int i = 1; i <= n; i++) G[i] = 1ll*qpow(2, 1ll*i*(i-1)/2%(P-1))*ifac[i]%P;

	G[0] = 1;

	F = poly_ln(G);

	printf("%d", 1ll*F[n]*fac[n]%P);

	return 0;

}

巴特西

[洛谷P4841][集训队作业2013]城市规划

题目大意

题解

代码

最新文章

热门文章