题面
(mathrm{bzoj})权限题
一句话题面
求(n)个点的无向连通图个数。
(nleq 130000)
题解
首先我们知道，(n)个点的无向图个数为(mathrm{g}(n) = 2^{mathrm{C}_n^2})
设(n)个点的无向连通图的个数为(mathrm{f}(n))
那么我们枚举(1)号点所在的连通块的大小(i)，可以知道
[mathrm{g}(n) = sum_{i=1}^n inom{n - 1}{i - 1} mathrm{f}(i)mathrm{g}(n-i)
]
拆开组合数：
[egin{aligned}
mathrm{g}(n) &= sum_{i=1}^n frac{(n-1)!}{(i-1)!(n-i)!}mathrm{f}(i)mathrm{g}(n-i) \
frac{mathrm{g}(n)}{(n-1)!} &= sum_{i=1}^n frac{mathrm{f}(i)}{(i-1)!} frac{mathrm{g}(n-i)}{(n-i)!}
end{aligned}
]
构造生成函数：
[egin{aligned}
mathcal{F}(x) &= sum_{i=1}^infty frac{mathrm{f}(i)}{(i-1)!}x^i \
mathrm{G_1}(x) &= sum_{i=0}^infty frac{mathrm{g}(i)}{i!}x^i \
mathrm{G_2}(x) &= sum_{i=1}^infty frac{mathrm{g}(i)}{(i-1)!}x^i
end{aligned}
]
那么(mathrm{G_2} = mathcal{F}*mathrm{G_1}, mathcal{F} = mathrm{G_1} * mathrm{G_2^{-1}})
多项式求逆即可
代码
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define RG register
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define clear(x, y) memset(x, y, sizeof(x))
inline int read()
{
int data = 0, w = 1; char ch = getchar();
while(ch != '-' && (!isdigit(ch))) ch = getchar();
if(ch == '-') w = -1, ch = getchar();
while(isdigit(ch)) data = data * 10 + (ch ^ 48), ch = getchar();
return data * w;
}
const int maxn(400010), Mod(1004535809);
int n, fac[maxn], inv[maxn], Pow[maxn];
int fastpow(int x, int y)
{
int ans = 1;
while(y)
{
if(y & 1) ans = 1ll * ans * x % Mod;
x = 1ll * x * x % Mod, y >>= 1;
}
return ans;
}
int r[maxn];
template<int opt> void FFT(int *p, int N)
{
for(RG int i = 0; i < N; i++) if(i < r[i]) std::swap(p[i], p[r[i]]);
for(RG int i = 1; i < N; i <<= 1)
{
int rot = fastpow(3, (Mod - 1) / (i << 1));
for(RG int j = 0; j < N; j += (i << 1))
for(RG int k = 0, w = 1; k < i; ++k, w = 1ll * w * rot % Mod)
{
int x = p[j + k], y = 1ll * w * p[i + j + k] % Mod;
p[j + k] = (x + y) % Mod, p[i + j + k] = (x - y + Mod) % Mod;
}
}
if(opt == -1) std::reverse(p + 1, p + N);
}
void Inv(int *a, int *b, int now)
{
static int c[maxn];
if(now == 1) return (void) (*b = fastpow(*a, Mod - 2));
Inv(a, b, (now + 1) >> 1); int P = -1, len = 1;
while(len < (now << 1)) len <<= 1, ++P;
for(RG int i = 0; i < len; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << P);
std::copy(a, a + now, c), std::fill(c + now, c + len, 0);
FFT<1>(c, len), FFT<1>(b, len);
for(RG int i = 0; i < len; i++)
b[i] = 1ll * (2 - 1ll * b[i] * c[i] % Mod + Mod) % Mod * b[i] % Mod;
FFT<-1>(b, len); int invn = fastpow(len, Mod - 2);
for(RG int i = 0; i < len; i++) b[i] = 1ll * b[i] * invn % Mod;
std::fill(b + now, b + len, 0);
}
int F[maxn], G1[maxn], G2[maxn], A[maxn];
int main()
{
#ifndef ONLINE_JUDGE
file(cpp);
#endif
n = read(), inv[0] = fac[0] = Pow[0] = Pow[1] = 1;
for(RG int i = 1; i <= n; i++) fac[i] = 1ll * fac[i - 1] * i % Mod;
inv[n] = fastpow(fac[n], Mod - 2);
for(RG int i = n - 1; i; i--) inv[i] = 1ll * inv[i + 1] * (i + 1) % Mod;
for(RG int i = 2; i <= n; i++)
Pow[i] = fastpow(2, 1ll * i * (i - 1) / 2 % (Mod - 1));
for(RG int i = 0; i <= n; i++) G1[i] = 1ll * Pow[i] * inv[i] % Mod;
for(RG int i = 1; i <= n; i++) G2[i] = 1ll * Pow[i] * inv[i - 1] % Mod;
Inv(G1, A, n + 1); int N = 1, P = -1;
while(N <= (n << 1)) N <<= 1, ++P;
for(RG int i = 0; i < N; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << P);
FFT<1>(A, N), FFT<1>(G2, N);
for(RG int i = 0; i < N; i++) F[i] = 1ll * A[i] * G2[i] % Mod;
FFT<-1>(F, N); int invn = fastpow(N, Mod - 2);
F[n] = 1ll * F[n] * invn % Mod;
printf("%lld
", 1ll * F[n] * fac[n - 1] % Mod);
return 0;
}