[题解] LuoguP4841 [集训队作业2013]城市规划

Description

求\(n\)个点无重边、无自环、带标号的无向联通图个数，对\(1004535809\)(\(479 \times 2^{21} + 1\))取模。\(n \le 130000\)

Solution

模数好像是在提示了......这个模数非常适合\(NTT\)。

还是想题吧。首先问自己一个问题：不要求联通会不会？不会

不连通的话最多有\(\binom{n}{2}\)条边，总方案数就是这些边选不选的问题，即\(2^{\binom{n}{2}}\)。

我们令不要求联通的\(n\)个点形成的简单无向图个数为\(g_n\)，联通图个数为\(f_n\)，不难发现有这个柿子

\[g_n = \sum\limits_{i=1}^n \binom{n-1}{i-1}f_ig_{n-i}
\]

意思是我枚举\(1\)号点所在联通块的大小，然后把这个联通快孤立起来，剩下的点随便连边。

看到这个柿子想卷积？有组合数不方便卷，我们观察到

\[\binom{n-1}{i-1} = \frac{(n-1)!}{(n-i)!(i-1)!}
\]

不妨把两边同时乘\(\frac{1}{(n-1)!}\)，然后再把剩下的分母分配一下

\[\frac{g_n}{(n-1)!} = \sum\limits_{i=1}^{n}\frac{f_i}{(i-1)!}\frac{g_{n-i}}{(n-i)!}
\]

这个柿子就非常好做，我们令\(h_n = \frac{g_n}{(n-1)!}\)，然后用\(\frac{f_n}{(n-1)!}\)代替\(f_n\)，\(\frac{g_n}{n!}\)代替\(g_n\)，分别得到\(h,f,g\)的生成函数

\[H(x) = \sum\limits_{n=0}^{\infty} h_nx^n
\]

\[F(x) = \sum\limits_{n=0}^{\infty} f_nx^n
\]

\[G(x) = \sum\limits_{n=0}^{\infty} g_nx^n
\]

显然有

\[H(x) = F(x)G(x)
\]

因为答案只与\(f_n\)有关，我们可以放到\(mod \ x^{n+1}\)下求\(F(x)\)。

即

\[F(x) \equiv G^{-1}(x)H(x) \ (mod \ x^{n+1})
\]

对\(G\)求逆过后与\(H\)卷积，就求出了\(F(x)\)，然后答案就是\(f_n \times (n-1)!\)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int P=1004535809,g=3,ig=334845270,N=500010;

inline int add(int x,int y){return x+y>=P?x+y-P:x+y;}

inline int sub(int x,int y){return x-y<0?x-y+P:x-y;}

inline int fpow(int x,int y){

	int ret=1; for (x%=P;y;y>>=1,x=1ll*x*x%P)

		if (y&1) ret=1ll*ret*x%P;

	return ret;

}

namespace Poly{

	int rev[N];

	void init(int limit){

		for (int i=0;i<limit;i++)

			rev[i]=rev[i>>1]>>1|((i&1)?limit>>1:0);

	}

	void ntt(int *f,int n,int flg){

		for (int i=0;i<n;i++) if (rev[i]<i) swap(f[i],f[rev[i]]);

		for (int k=1,len=2;len<=n;len<<=1,k<<=1){

			int wn=fpow(flg==1?g:ig,(P-1)/len);

			for (int i=0;i<n;i+=len){

				for (int w=1,j=i;j<i+k;j++,w=1ll*w*wn%P){

					int tmp=1ll*w*f[j+k]%P;

					f[j+k]=sub(f[j],tmp),f[j]=add(f[j],tmp);

				}

			}

		}

		if (flg==-1){

			int inv=fpow(n,P-2);

			for (int i=0;i<n;i++) f[i]=1ll*f[i]*inv%P;

		}

	}

	int F[N];

	void getinv(int *f,int n,int *G){

		if (n==1){G[0]=fpow(f[0],P-2);return;}

		getinv(f,(n+1)>>1,G);

		int limit=1; while(limit<=2*n)limit<<=1; init(limit);

		for (int i=0;i<n;i++) F[i]=f[i];

//		cout<<"wtf: "; for (int i=0;i<n;i++) cout<<G[i]<<" "; cout<<endl;

		for (int i=n;i<limit;i++) F[i]=G[i]=0;

		ntt(F,limit,1),ntt(G,limit,1);

		for (int i=0;i<limit;i++) G[i]=1ll*G[i]*sub(2,1ll*F[i]*G[i]%P)%P;

		ntt(G,limit,-1);

		for (int i=n;i<limit;i++) G[i]=0;

	}

}

using Poly::ntt;

using Poly::getinv;

int G[N],iG[N],H[N],F[N];

int ifac[N],inv[N],fac[N];

int main(){

	int n; scanf("%d",&n);

	fac[0]=fac[1]=ifac[0]=ifac[1]=1,inv[1]=1;

	for (int i=2;i<=n;i++){

		inv[i]=1ll*inv[P%i]*(P-P/i)%P;

		ifac[i]=1ll*ifac[i-1]*inv[i]%P;

		fac[i]=1ll*fac[i-1]*i%P;

	}

	G[0]=1;

	for (int i=1;i<=n;i++)

		G[i]=1ll*fpow(2,1ll*i*(i-1)/2%(P-1))*ifac[i]%P,H[i]=1ll*G[i]*i%P;

	getinv(G,n+1,iG);

	int limit=1; while(limit<=2*n)limit<<=1; Poly::init(limit);

	ntt(iG,limit,1),ntt(H,limit,1);

	for (int i=0;i<limit;i++) F[i]=1ll*iG[i]*H[i]%P;

	ntt(F,limit,-1);

	printf("%d\n",1ll*F[n]*fac[n-1]%P);

	return 0;

}

巴特西

[题解] LuoguP4841 [集训队作业2013]城市规划

Description

Solution

最新文章

热门文章