Description：

求 $n$ 个点的简单无向连通图数目模 $1004535809$ 的值。

$1\leqslant n\leqslant 1.3\times 10^5$

Solution：

设 $f[i]$ 表示 $n$ 个点的简单无向连通图数目， $g[i]$ 不要求联通，显然有 $g[i]=2^{C^2_n}$ ，那么转移时就可以枚举最后一个点所在联通块的大小： $$ f[i]=g[i]-\sum_{j=1}^{i-1}f[j]\times C_{i-1}^{j-1}\times g[i-j] $$ 经典的连通图计数问题。这样做是 $O(n^2)$ 的，要用一些手段来优化。

肯定要把组合数拆开，两侧同除 $(i-1)!$ ，得： $$ \frac{f[i]}{(i-1)!}=\frac{g[i]}{(i-1)!}-\sum_{j=1}^{i-1}\frac{f[j]}{(j-1)!}\frac{g[i-j]}{(i-j)!} $$ 这个时候虽然式子还是很混乱，但是我们已经去掉了组合数，得到了 $\frac{f[x]}{(x-1)!}$ 的阶乘的形式。

再移项，会发现两部分是可以合并的： $$ \frac{g[i]}{(i-1)!}=\sum_{j=1}^i\frac{f[j]}{(j-1)!}\frac{g[i-j]}{(i-j)!} $$ 这个时候我们的式子已经非常优美了，成为了一个标准的卷积的形式。

考虑生成函数，设： $$ \begin{align} A&=\sum_{i=1}^n\frac{f[i]}{(i-1)!}\\ B&=\sum_{i=0}^n\frac{g[i]}{i!}\\ C&=\sum_{i=1}^n\frac{g[i]}{(i-1)!} \end{align} $$ 这时我们有 $A\times B=C$ ，然后有 $A\equiv C\times B^{-1}(\mod x^{n+1})$ ，多项式求逆就可以了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 520010

#define P 1004535809

typedef long long ll;

ll fac[MAXN];

ll G[MAXN];

ll power(ll a,ll b)

{

	ll res = 1;

	while(b > 0)

	{

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

		a = a * a % P;

		b = b >> 1;

	}

	return res;

}

ll A[MAXN],B[MAXN],C[MAXN];

ll inv(ll k){return power(k,P - 2);}

ll ww[MAXN << 1],*g = ww + MAXN;

int rev[MAXN];

void NTT(ll f[],int l,int type)

{

	for(int i = 0;i < l;++i)

	{

		if(i < rev[i])swap(f[i],f[rev[i]]);

	}

	for(int i = 2;i <= l;i = i << 1)

	{

		ll wn = g[type * l / i];

		for(int j = 0;j < l;j += i)

		{

			ll w = 1;

			for(int k = j;k < j + i / 2;++k)

			{

				ll u = f[k],t = w * f[k + i / 2] % P;

				f[k] = (u + t) % P;

				f[k + i / 2] = (u - t + P) % P;

				w = w * wn % P;

			}

		}

	}

	if(type == -1)

	{

		ll invl = inv(l);

		for(int i = 0;i < l;++i)f[i] = f[i] * invl % P;

	}

	return;

}

ll c[MAXN];

void calc_inv(int deg,ll a[],ll b[])

{

	if(deg == 1)

	{

		b[0] = inv(a[0]);

		return;

	}

	calc_inv((deg + 1) / 2,a,b);

	int l = 0,len = 1;

	for(;len < deg * 2;len = len << 1,++l);

	for(int i = 0;i < len;++i)rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));

	g[0] = g[-len] = 1;g[1] = g[1 - len] = power(3,(P - 1) / len);

	for(int i = 2;i < len;++i)g[i] = g[i - len] = g[i - 1] * g[1] % P;

	for(int i = 0;i < deg;++i)c[i] = a[i];

	for(int i = deg;i < len;++i)c[i] = 0;

	NTT(b,len,1);NTT(c,len,1);

	for(int i = 0;i < len;++i)

	{

		b[i] = (2 * b[i] % P - c[i] * b[i] % P * b[i] % P + P) % P;

	}

	NTT(b,len,-1);

	for(int i = deg;i < len;++i)b[i] = 0;

	return;

}

int main()

{

	scanf("%d",&n);

	fac[0] = 1;for(int i = 1;i <= n;++i)fac[i] = fac[i - 1] * i % P;

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

	for(int i = 0;i <= n;++i)B[i] = G[i] * inv(fac[i]) % P;

	for(int i = 1;i <= n;++i)C[i] = G[i] * inv(fac[i - 1]) % P;

	calc_inv(n + 1,B,A);

	int l = 0,len = 1;

	for(;len <= n * 2;len = len << 1,++l);

	for(int i = 0;i < len;++i)rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));

	g[0] = g[-len] = 1;g[1] = g[1 - len] = power(3,(P - 1) / len);

	for(int i = 2;i < len;++i)g[i] = g[i - len] = g[i - 1] * g[1] % P;

	NTT(A,len,1);NTT(C,len,1);

	for(int i = 0;i < len;++i)

	{

		A[i] = A[i] * C[i] % P;

	}

	NTT(A,len,-1);

	printf("%lld\n",A[n] * fac[n - 1] % P);

	return 0;

}