题目描述
刚刚解决完电力网络的问题，阿狸又被领导的任务给难住了。
刚才说过，阿狸的国家有 \(n\) 个城市，现在国家需要在某些城市对之间建立一些贸易路线，使得整个国家的任意两个城市都直接或间接的连通。
为了省钱, 每两个城市之间最多只能有一条直接的贸易路径。对于两个建立路线的方案，如果存在一个城市对，在两个方案中是否建立路线不一样，那么这两个方案就是不同的，否则就是相同的。现在你需要求出一共有多少不同的方案。
好了，这就是困扰阿狸的问题。换句话说，你需要求出 \(n\) 个点的简单 (无重边无自环) 有标号无向连通图数目。
由于这个数字可能非常大, 你只需要输出方案数对 \(1004535809 ( 479 \times 2 ^{21} + 1 )\) 即可。
数据范围：\(n\leq 130000\) 。
solution
多项式的经典题了。
首先设 \(f(i)\) 表示 \(n\) 个点有标号无向连通图的个数，\(g(i)\) 表示 \(i\) 个点的无向图（可以不连通）的个数, 根据小学知识可得：\(g(n) = 2^{n\choose 2}\) ，则有：
\(g(n) = \displaystyle\sum_{i=1}^{n} f(i) \times {n-1\choose i-1}\times g(n-i)\)
这个可以怎么理解呢？我们可以枚举 \(1\) 所在的联通块的个数 \(i\), 首先要从剩下的 \(n-1\) 个点里面选 \(i-1\) 个点来构成这个联通块，方案数即为 \(n-1\choose i-1\) 。然后这 \(i\) 个点组成的有标号无向连通图的个数为 \(f(i)\), 剩下的 \(n-i\) 个点随便连，方案数为 \(g(n-i)\) 。然后就有了我们上面的那个柿子。
我们尝试把组合数拆开来构成卷积则有：
\(g(n) = \displaystyle\sum_{i=1}^{n} f(i)\times {(n-1)!\over (i-1)!(n-i)!}\times g(n-i)\)
把 \((n-1)!\) 提出来移到左边可得：
\(\displaystyle {g(n)\over (n-1)!} = \displaystyle\sum_{i=1}^{n} {f(i)\over (i-1)!} \times {g(n-i)\over (n-i)!}\)
上面的柿子是个很明显的卷积式，考虑构造多项式 \(A(x),B(x),C(x)\) 其中：
\(\displaystyle A(x) = \displaystyle\sum_{i=0}^{n} {g(i)\over (n-1)!} x^i\)
\(\displaystyle B(x) = \sum_{i-0}^{n} {f(i)\over (i-1)!} x^i\)
\(C(x) = \displaystyle\sum_{i=0}^{n} {g(i)\over i!} x^i\)
则有 \(A(x) = B(x) * C(x)\) ，那么 \(B(x) = C(x) * A(x)^{-1}\) 。
我们求出 \(A(x)\) 的乘法逆，在卷上 \(C(x)\) 就可以得到 \(B(x)\) 每一项的系数。
最后的答案即为 \([x^n] B(x) \times (n-1)!\) 。
坑点：注意多项式的求逆操作要保证多项式的项数在 \(2\) 的整次幂的时候进行，（我在这里卡了好久）。
Code
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
const int N = 5e5+10;
const int p = 1004535809;
int n,rev[N],jz[N],inv[N],a[N],b[N],c[N],d[N],base[N];
inline int read()
{
int s = 0, w = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}
return s * w;
}
int ksm(int a,int b)
{
int res = 1;
for(; b; b >>= 1)
{
if(b & 1) res = res * a % p;
a = a * a % p;
}
return res;
}
void NTT(int *a,int lim,int opt)
{
for(int i = 0; i < lim; i++)
{
if(i < rev[i]) swap(a[i],a[rev[i]]);
}
for(int h = 1; h < lim; h <<= 1)
{
int wn = ksm(3,(p-1)/(h<<1));
if(opt == -1) wn = ksm(wn,p-2);
for(int j = 0; j < lim; j += (h<<1))
{
int w = 1;
for(int k = 0; k < h; k++)
{
int u = a[j + k];
int v = w * a[j + h + k] % p;
a[j + k] = (u + v) % p;
a[j + h + k] = (u - v + p) % p;
w = w * wn % p;
}
}
}
if(opt == -1)
{
int INV = ksm(lim,p-2);
for(int i = 0; i < lim; i++) a[i] = a[i] * INV % p;
}
}
void Inv(int *a,int *b,int n)
{
if(n == 1)
{
b[0] = ksm(a[0],p-2);
return;
}
Inv(a,b,(n+1)>>1);
int lim = 1, tim = 0;
while(lim < (n<<1)) lim <<= 1, tim++;
for(int i = 0; i < lim; i++) rev[i] = (rev[i>>1]>>1) | ((i&1)<<(tim-1));
for(int i = 0; i < n; i++) c[i] = a[i];
for(int i = n; i < lim; i++) c[i] = 0;
NTT(c,lim,1); NTT(b,lim,1);
for(int i = 0; i < lim; i++) b[i] = (2 * b[i] % p - c[i] * b[i] % p * b[i] % p + p) % p;
NTT(b,lim,-1);
for(int i = n; i < lim; i++) b[i] = 0;
}
signed main()
{
n = read();
jz[0] = inv[0] = 1; base[0] = 1;
for(int i = 1; i <= n; i++) jz[i] = jz[i-1] * i % p;
inv[n] = ksm(jz[n],p-2);
for(int i = n-1; i >= 1; i--) inv[i] = inv[i+1] * (i+1) % p;
for(int i = 1; i <= n; i++) base[i] = ksm(2,i*(i-1)/2);
for(int i = 1; i <= n; i++) a[i] = base[i] * inv[i-1] % p;
for(int i = 0; i <= n; i++) d[i] = base[i] * inv[i] % p;
int len = 1;
while(len <= n) len <<= 1;
Inv(d,b,len);
int lim = 1, tim = 0;
while(lim < (n<<1)) lim <<= 1, tim++;
for(int i = 0; i < lim; i++) rev[i] = (rev[i>>1]>>1) | ((i&1)<<(tim-1));
NTT(a,lim,1); NTT(b,lim,1);
for(int i = 0; i < lim; i++) a[i] = a[i] * b[i] % p;
NTT(a,lim,-1);
printf("%lld\n",a[n]*jz[n-1]%p);
return 0;
}