题目描述
刚刚解决完电力网络的问题，阿狸又被领导的任务给难住了。
刚才说过，阿狸的国家有 (n) 个城市，现在国家需要在某些城市对之间建立一些贸易路线，使得整个国家的任意两个城市都直接或间接的连通。
为了省钱, 每两个城市之间最多只能有一条直接的贸易路径。对于两个建立路线的方案，如果存在一个城市对，在两个方案中是否建立路线不一样，那么这两个方案就是不同的，否则就是相同的。现在你需要求出一共有多少不同的方案。
好了，这就是困扰阿狸的问题。换句话说，你需要求出 (n) 个点的简单 (无重边无自环) 有标号无向连通图数目。
由于这个数字可能非常大, 你只需要输出方案数对 (1004535809 ( 479 imes 2 ^{21} + 1 )) 即可。
数据范围：(nleq 130000) 。
solution
多项式的经典题了。
首先设 (f(i)) 表示 (n) 个点有标号无向连通图的个数，(g(i)) 表示 (i) 个点的无向图（可以不连通）的个数, 根据小学知识可得：(g(n) = 2^{nchoose 2}) ，则有：
(g(n) = displaystylesum_{i=1}^{n} f(i) imes {n-1choose i-1} imes g(n-i))
这个可以怎么理解呢？我们可以枚举 (1) 所在的联通块的个数 (i), 首先要从剩下的 (n-1) 个点里面选 (i-1) 个点来构成这个联通块，方案数即为 (n-1choose i-1) 。然后这 (i) 个点组成的有标号无向连通图的个数为 (f(i)), 剩下的 (n-i) 个点随便连，方案数为 (g(n-i)) 。然后就有了我们上面的那个柿子。
我们尝试把组合数拆开来构成卷积则有：
(g(n) = displaystylesum_{i=1}^{n} f(i) imes {(n-1)!over (i-1)!(n-i)!} imes g(n-i))
把 ((n-1)!) 提出来移到左边可得：
(displaystyle {g(n)over (n-1)!} = displaystylesum_{i=1}^{n} {f(i)over (i-1)!} imes {g(n-i)over (n-i)!})
上面的柿子是个很明显的卷积式，考虑构造多项式 (A(x),B(x),C(x)) 其中：
(displaystyle A(x) = displaystylesum_{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) = displaystylesum_{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) imes (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
",a[n]*jz[n-1]%p);
return 0;
}