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

题目描述

思路

套路题。

设 $f_i$ 表示由 $i$ 个点所组成的联通无向图个数， $g_i$ 表示由 $i$ 个点组成的无向图个数，不保证联通。

由于没有重边与自环， $i$ 个点最多有 $\binom{n}{2}$ 条边，则有 $g_i = 2^{\binom{n}{2}}$ 。

考虑 $g_i$ 怎么表示，枚举 $i$ 号点所在的连通块大小，则有：

g_n = \sum_{i=1}^n\binom{n-1}{i-1}f_ig_{n-i}

\Rightarrow \frac{2^{\binom{n}{2}}}{(n-1)!} = \sum_{i=1}^n\frac{f_i}{(i-1)!}\cdot\frac{2^\binom{{n-i}}{2}}{(n-i)!}

这个东西看起来就很 OGF。

设

F(x) = \sum_{n=1}^\infty \frac{f_n}{(n-1)!}x^n

G(x) = \sum_{n=1}^\infty \frac{2^{\binom{n}{2}}}{n!}x^n

H(x) = \sum_{i=1}^\infty \frac{2^\binom{{n}}{2}}{(n-1)!}x^n

显然有：

H(x) = F(x) \times G(x) \Leftrightarrow F(x) = H(x) \times G^{-1}(x)

直接多项式求逆即可。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1004535809, g = 3, MAXN = 130000 << 4;

ll qpow(ll a, ll b) {
	ll res = 1;
	while (b) {
		if (b & 1ll) res = res * a % mod;
		a = a * a % mod;
		b >>= 1ll;
	}
	return res;
}

int r[MAXN];

int limit;
void init(int l) {
	for (int i = 0; i < limit; i++)
		r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
}

void NTT(ll* f, int type) {
	for (int i = 0; i < limit; i++)
		if (i < r[i])
			swap(f[i], f[r[i]]);
	
	for (int mid = 1; mid < limit; mid <<= 1) {
		ll W = qpow(g, (mod - 1) / (mid << 1));
		if (type == -1) W = qpow(W, mod - 2);
		for (int R = mid << 1, j = 0; j < limit; j += R) {
			ll w = 1;
			for (int k = 0; k < mid; k++, w = w * W % mod) {
				ll x = f[j + k], y = w * f[j + k + mid] % mod;
				f[j + k] = (x + y) % mod;
				f[j + k + mid] = (x - y + mod) % mod;
			}
		}
	}

	if (type == 1) return;
	ll inv = qpow(limit, mod - 2);
	for (int i = 0; i < limit; i++)
		f[i] = (f[i] * inv + mod) % mod;
}

ll c[MAXN];


void GetInv(ll* f, ll* g, int n) {
	if (n == 1) {
		g[0] = qpow(f[0], mod - 2);
		return;
	}
	GetInv(f, g, n + 1 >> 1);
	limit = 1;
	int l = 0;
	while (limit <= n + n) limit <<= 1, l++;
	init(l);
	for (int i = 0; i < n; i++) c[i] = f[i];
	for (int i = n; i < limit; i++) c[i] = 0;
	NTT(c, 1);
	NTT(g, 1);
	for (int i = 0; i < limit; i++)
		g[i] = ((2ll - g[i] * c[i] % mod) + mod) % mod * g[i] % mod;
	NTT(g, -1);
	for (int i = n; i < limit; i++)
		g[i] = 0;
}

ll F[MAXN], G[MAXN], H[MAXN], _G[MAXN];
ll Fiv[MAXN], InvFiv[MAXN];
ll N;

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> N;
	N++;
	Fiv[0] = InvFiv[0] = 1;
	for (int i = 1; i <= N; i++) {
		Fiv[i] = Fiv[i - 1] * i % mod;
		InvFiv[i] = qpow(Fiv[i], mod - 2);
	}
	for (int i = 0; i < N; i++) {
		G[i] = qpow(2, 1ll * i * (i - 1) / 2 % (mod - 1)) * InvFiv[i] % mod;
		if (i) H[i] = qpow(2, 1ll * i * (i - 1) / 2 % (mod - 1)) * InvFiv[i - 1] % mod;
	}
	
	GetInv(G, _G, N);

	limit = 1;
	int l = 0;
	while (limit <= N * 2) limit <<= 1, l++;
	NTT(_G, 1); NTT(H, 1);
	for (int i = 0; i < limit; i++) F[i] = _G[i] * H[i] % mod;
	NTT(F, -1);
	N--;
	cout << F[N] * Fiv[N - 1] % mod << endl;
	return 0;
}