FFT神仙题，强烈建议先自己推一推式子再看题解。
首先正着想比较难想，正难则反，所以我们先考虑一下全集。设(displaystyle g[n]=2^{C_n^2})(C为组合数),表示n个有标号的点随便连边的方案数，设(f[n])是n个有标号的点的无向连通图的方案数。
考虑(g)和(f)之间的关系，因为每一个点都不一样，所以我们枚举1号点所在连通图的大小就可以得到
(displaystyle f[n]=g[n]-sum_{i=1}^{n-1}C_{n-1}^{i-1}f[i]g[n-i]),
后面的(sum_{i=1}^{n-1}C_{n-1}^{i-1}f[i]g[n-i])是枚举1号点所在联通块的大小，注意这里i不能等于n，因为等于n的时候它是一个连通图。
我们将等号两边转移一下得到
(displaystyle g[n]=sum_{i=1}^{n-1}C_{n-1}^{i-1}f[i]g[n-i]+f[n])
因为(i=n)时，(C_{n-1}^{n-1}f[n]g[0]=f[n]),所以
(displaystyle g[n]=sum_{i=1}^{n}C_{n-1}^{i-1}f[i]g[n-i])
我们知道(displaystyle C_n^m=frac{n!}{m!(n-m)!}),所以
(displaystyle g[n]=sum_{i=1}^{n}(n-1)!frac{f[i]}{(i-1)!}frac{g[n-i]}{(n-i)!})
因为((n-1)!)和(i)无关。所以
(displaystyle g[n]=(n-1)!sum_{i=1}^{n}frac{f[i]}{(i-1)!}frac{g[n-i]}{(n-i)!})
(displaystyle frac{g[n]}{(n-1)!}=sum_{i=1}^{n}frac{f[i]}{(i-1)!}frac{g[n-i]}{(n-i)!})
我们设(displaystyle H[n]=frac{g[n]}{(n-1)!}) (displaystyle F[n]=frac{f[n]}{(n-1)!}) (displaystyle G[n]=frac{g[n]}{n!})
就能得到
(displaystyle H[n]=sum_{i=1}^nF[i]G[n-i])
又因为(i=0)时(F[i]=0).所以
(displaystyle H[n]=sum_{i=0}^nF[i]G[n-i])
(displaystyle H=F*G)
(displaystyle F=frac{H}{G})
(displaystyle F=HG^{-1})
因为 (H)和(G)已知的，所以我们多项式求个逆就OK啦。
时间复杂度(O(nlogn))。
#include<bits/stdc++.h>
#define LL long long
using namespace std;
int n;
const int N = 500010, mod = 1004535809, YY = 3, YYinv = (mod + 1) / 3;
int r[N];
LL c[N], jc[N], inv[N], F[N], G[N], Ginv[N], H[N];
int read()
{
int x = 0; int f = 0; char c = getchar();
while (!isdigit(c)) f |= c == '-', c = getchar();
while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
return f ? -x : x;
}
LL ksm(LL a, LL b, LL mod)
{
LL res = 1;
for (; b; b >>= 1, a = a * a % mod)
if (b & 1)res = res * a % mod;
return res;
}
void NTT(LL *A, int lim, int opt)
{
for (int i = 0; i < lim; ++i)r[i] = (r[i >> 1] >> 1) | ((i & 1) ? (lim >> 1) : 0);
for (int i = 0; i < lim; ++i)
if (i < r[i])swap(A[i], A[r[i]]);
int len;
LL wn, w, x, y;
for (int mid = 1; mid < lim; mid <<= 1)
{
len = mid << 1;
wn = ksm(opt == 1 ? YY : YYinv, (mod - 1) / len, mod);
for (int j = 0; j < lim; j += len)
{
w = 1;
for (int k = j; k < j + mid; ++k, w = w * wn % mod)
{
x = A[k]; y = A[k + mid] * w % mod;
A[k] = (x + y) % mod;
A[k + mid] = (x - y + mod) % mod;
}
}
}
if (opt == 1)return;
LL ni = ksm(lim, mod - 2, mod);
for (int i = 0; i < lim; ++i)A[i] = A[i] * ni % mod;
}
void MUL(LL*A, int n, LL *B, int m)
{
int lim = 1;
while (lim <= (n + m))lim <<= 1;
NTT(A, lim, 1); NTT(B, lim, 1);
for (int i = 0; i < lim; ++i)A[i] = A[i] * B[i] % mod;
NTT(A, lim, -1);
}
void INV(int siz, LL *A, LL *B)
{
if (siz == 1)
{
B[0] = ksm(A[0], mod - 2, mod);
return;
}
INV((siz + 1) >> 1, A, B);
int lim = 1;
while (lim < (siz << 1))lim <<= 1;
for (int i = 0; i < siz; ++i)c[i] = A[i];
for (int i = siz; i < lim; ++i)c[i] = 0;
NTT(c, lim, 1); NTT(B, lim, 1);
for (int i = 0; i < lim; ++i)B[i] = B[i] * (2 - c[i] * B[i] % mod + mod) % mod;
NTT(B, lim, -1);
for (int i = siz; i < lim; ++i)B[i] = 0;
}
void YYCH()
{
jc[0] = jc[1] = inv[0] = inv[1] = 1;
for (int i = 1; i <= n; ++i)jc[i] = jc[i - 1] * i % mod;
inv[n] = ksm(jc[n], mod - 2, mod);
for (int i = n - 1; i >= 1; --i)inv[i] = inv[i + 1] * (i + 1) % mod;
for (int i = 0; i <= n; ++i)G[i] = ksm(2, (LL)i * (i - 1) / 2, mod) * inv[i] % mod;
for (int i = 1; i <= n; ++i)H[i] = ksm(2, (LL)i * (i - 1) / 2, mod) * inv[i - 1] % mod;
}
signed main()
{
cin >> n;
YYCH();
INV(n + 1, G, Ginv);
MUL(H, n, Ginv, n);
cout << H[n]*jc[n - 1] % mod;
return 0;
}