题目
Description
刚刚解决完电力网络的问题, 阿狸又被领导的任务给难住了.
刚才说过, 阿狸的国家有n个城市, 现在国家需要在某些城市对之间建立一些贸易路线, 使得整个国家的任意两个城市都直接或间接的连通. 为了省钱, 每两个城市之间最多只能有一条直接的贸易路径. 对于两个建立路线的方案, 如果存在一个城市对, 在两个方案中是否建立路线不一样, 那么这两个方案就是不同的, 否则就是相同的. 现在你需要求出一共有多少不同的方案.
好了, 这就是困扰阿狸的问题. 换句话说, 你需要求出n个点的简单(无重边无自环)无向连通图数目. 由于这个数字可能非常大, 你只需要输出方案数mod 1004535809(479 * 2 ^ 21 + 1)即可.
Input
仅一行一个整数n(<=130000)
Output
仅一行一个整数, 为方案数 mod 1004535809.
Sample Input
3
Sample Output
4
HINT
对于 100%的数据, n <= 130000
题解
如果要求$n$个点形成的图,那么答案就是$\sum_{i=0}^{C_{n}^{2}}C_{C_{2}^{n}}^i$,即$2^{\frac{n(n-1)}{2}}$
发现所有的图的个数等于某些点形成连通图,其他点任意连的方案数之和
如果设$F(n)=2^{\frac{n(n-1)}{2}}$,$f(n)$表示$n$个点形成连通图的方案数,则有
$F(n)=\sum_{i=1}^{n}f(i)F(n-i)C_{n-1}^{i-1}$
可以这么理解这个式子:$1$号节点肯定要在一个连通块之内,所有考虑枚举$1$号节点所在连通块大小,这样$i$个节点时共有$C_{n-1}^{i-1}$种情况,同时乘上其他随意连的点的方案数
可以把$C_{n-1}^{i-1}$拆开,然后就是$\frac{F(n)}{(n-1)!}=\sum_{i=1}^{n}\frac{f(i)}{(i-1)!}\frac{F(n-i)}{(n-i)!}$
看成$3$个多项式,然后就可以多项式求逆求出$f(x)$了
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define LL long long
using namespace std;
const int MAX=5.3e5+5,mod=1004535809;
int n,lim=1,L;
int R[MAX],a[MAX],b[MAX],A[MAX],_A[MAX],fac[MAX],Fac[MAX];
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
int Pow(int a,LL b)
{
int ans=1;
for(;b;b>>=1,a=1ll*a*a%mod)
if(b&1) ans=1ll*a*ans%mod;
return ans;
}
void NTT(int *A,int tt=1)
{
for(int i=0;i<lim;++i)
if(i<R[i]) swap(A[i],A[R[i]]);
for(int i=1,w1;i<lim;i<<=1)
{
w1=Pow(3,(mod-1)/(i<<1));
for(int l=i<<1,w,j=0;j<lim;j+=l)
{
w=1;
for(int k=0,x,y;k<i;++k,w=1ll*w*w1%mod)
{
x=A[j+k],y=1ll*w*A[i+j+k]%mod,A[j+k]=x+y,A[i+j+k]=x-y+mod;
if(A[j+k]>=mod) A[j+k]-=mod;
if(A[i+j+k]>=mod) A[i+j+k]-=mod;
}
}
}
if(tt==-1)
{
reverse(A+1,A+lim);
for(int i=0,G=Pow(lim,mod-2);i<lim;++i)
A[i]=1ll*A[i]*G%mod;
}
}
void Inv(int *A,int *b,int n)
{
if(n==1) return void(b[0]=Pow(A[0],mod-2));
Inv(A,b,n+1>>1),lim=1,L=0;
while(lim<=2*n-1) lim<<=1,++L;
for(int i=0;i<=lim;++i)
R[i]=(R[i>>1]>>1)|((i&1)<<L-1),a[i]=0;
for(int i=0;i<n;++i)
a[i]=A[i];
NTT(a),NTT(b);
for(int i=0;i<=lim;++i)
b[i]=(2-1ll*a[i]*b[i]%mod+mod)%mod*b[i]%mod;
NTT(b,-1);
for(int i=n;i<=lim;++i)
b[i]=0;
}
int main()
{
n=read(),fac[0]=1,Fac[0]=Pow(1,mod-2);
for(int i=0;i<=n;++i)
{
if(i) fac[i]=1ll*fac[i-1]*i%mod,Fac[i]=Pow(fac[i],mod-2);
A[i]=1ll*Pow(2,1ll*i*(i-1)>>1)*Fac[i]%mod,_A[i]=1ll*A[i]*i%mod;
}
Inv(A,b,n);
while(lim<=2*n-1) lim<<=1,++L;
for(int i=0;i<=lim;++i)
R[i]=(R[i>>1]>>1)|((i&1)<<L-1);
NTT(_A),NTT(b);
for(int i=0;i<=lim;++i)
_A[i]=1ll*_A[i]*b[i]%mod;
return NTT(_A,-1),printf("%d",1ll*_A[n]*fac[n-1]%mod),0;
}