P4841 [集训队作业2013]城市规划

题目大意

给你$n$个点，编号分别为$1,2,\dots ,n$，求这$n$个点构成的无向连通图的数目，对$1004535809$取模。

$1\le n\le 130000$

题解

前置知识：多项式乘法逆

设$f(n)$表示点数为$n$的无向连通图的数量，$g(n)$表示点数为$n$的无向图的数量。

则有$g(n)=2^{C_n^2}$。

那么枚举一号节点所在的连通块，得

$$g(n)=\sum _{i=1}^n{C}_{n-1}^{i-1}\cdot f(i)\cdot g(n-i)$$

将$g(n)=2^{C_n^2}$代入得

$$2^{C_n^2}=\sum _{i=1}^n{C}_{n-1}^{i-1}\cdot f(i)\cdot 2^{C_{n-i}^2}$$

$$\frac{2^{C_n^2}}{(n-1)!}=\sum _{i=1}^n\frac{f(i)}{(i-1)!}\cdot \frac{2^{C_{n-i}^2}}{(n-i)!}$$

定义多项式$F(x),G(x),H(x)$，令

• $F$的第$n$项的系数为$\frac{f(n)}{(n-1)!}$
• $G$的第$n$项的系数为$\frac{2^{C_n^2}}{n!}$
• $H$的第$n$项的系数为$\frac{2^{C_n^2}}{(n-1)!}$

则

$$F=H\times G^{-1}(\mathrm{mod}{x}^{n+1})$$

$G$和$H$都可以$O(n)$求出，再用多项式乘法逆即可求出$F$。

时间复杂度为$O(n{\log }^{2}n)$。

code

#include<bits/stdc++.h>
using namespace std;
long long w,wn,jc[500005],ny[500005],f[500005],g[500005],h[500005],a1[500005];
const int N=500000;
const long long G=3,mod=1004535809;
long long mi(long long t,long long v){
	if(!v) return 1;
	long long re=mi(t,v/2);
	re=re*re%mod;
	if(v&1) re=re*t%mod;
	return re;
}
void init(){
	jc[0]=1;
	for(int i=1;i<=N;i++) jc[i]=jc[i-1]*i%mod;
	ny[N]=mi(jc[N],mod-2);
	for(int i=N-1;i>=0;i--) ny[i]=ny[i+1]*(i+1)%mod;
}
void ch(long long *a,int l){
	for(int i=1,j=l/2;i<l-1;i++){
		if(i<j) swap(a[i],a[j]);
		int k=l/2;
		while(j>=k){
			j-=k;k>>=1;
		}
		j+=k;
	}
}
void ntt(long long *a,int l,int fl){
	for(int i=2;i<=l;i<<=1){
		if(fl==1) wn=mi(G,(mod-1)/i);
		else wn=mi(G,mod-1-(mod-1)/i);
		for(int j=0;j<l;j+=i){
			w=1;
			for(int k=j;k<j+i/2;k++,w=w*wn%mod){
				long long t=a[k],u=w*a[k+i/2]%mod;
				a[k]=(t+u)%mod;
				a[k+i/2]=(t-u+mod)%mod;
			}
		}
	}
	if(fl==-1){
		long long ny=mi(l,mod-2);
		for(int i=0;i<l;i++) a[i]=a[i]*ny%mod;
	}
}
void solve(int l){
	if(l==1){
		g[0]=mi(f[0],mod-2);
		return;
	}
	solve((l+1)/2);
	int len=1;
	while(len<2*l) len<<=1;
	for(int i=0;i<l;i++) a1[i]=f[i];
	for(int i=l;i<len;i++) a1[i]=0;
	ch(a1,len);ch(g,len);
	ntt(a1,len,1);ntt(g,len,1);
	for(int i=0;i<len;i++){
		g[i]=(2-a1[i]*g[i]%mod+mod)%mod*g[i]%mod;
	}
	ch(g,len);ntt(g,len,-1);
	for(int i=l;i<len;i++) g[i]=0;
}
int main()
{
	init();
	int n;
	scanf("%d",&n);
	for(int i=0;i<=n;i++){
		f[i]=mi(2,1ll*i*(i-1)/2)*ny[i]%mod;
		h[i]=mi(2,1ll*i*(i-1)/2)*ny[i-1]%mod;
	}
	solve(n+1);
	int len=1;
	while(len<=n) len<<=1;
	ch(g,len);ch(h,len);
	ntt(g,len,1);ntt(h,len,1);
	for(int i=0;i<=len;i++) f[i]=g[i]*h[i]%mod;
	ch(f,len);
	ntt(f,len,-1);
	printf("%lld",f[n]*jc[n-1]%mod);
	return 0;
}