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

所以，到底用没用了生成函数的知识？

upd on 2023.6.6：现在有指数生成函数做法了，不过不在这里，在“生成函数”一文的例题中。

之前在蓝书上看到过一点这类题的 DP 做法。结果感觉这题的做法有点类似，只不过变成卷积来求，反而跟生成函数没有太大的联系（？）。

设计两个函数 $f(x),g(x)$ 分别表示有标号的无向图和有标号的无向连通图。考虑这类问题的经典套路，固定点 $1$，枚举点 $1$ 所在连通块大小，可以得到关系式：

$$g(x)=\sum_{i=1}^x {\binom{x-1}{i-1} f(i)g(x-i)}$$

显然有 $g(x)=2^{\binom{x}{2}}$，将其带入并做一些变换：

$$2^{\binom{x}{2}}=\sum_{i=1}^x {\binom{x-1}{i-1} f(i)2^{\binom{n-i}{2}}}\\ \frac {2^{\binom{x}{2}}}{(n-1)!}=\sum_{i=1}^x {\frac{f(i)2^{\binom{n-i}{2}}}{(i-1)!(n-i)!}}$$

这就变成类似卷积的形式了，为了更好的操作，我们另外设计几个函数：

$$F(x)=\frac{f(x)}{(x-1)!}\\ G(x)=\frac{2^{\binom{n-x}{2}}}{x!}\\ H(x)=\frac{2^{\binom{n-x}{2}}}{(x-1)!}$$

我们明显有：

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

对 $G(x)$ 求逆再和 $H(x)$ 卷积就得到了 $F(x)$。

Code

#include<iostream>
#include<cstdio>
using namespace std;
const int N=5e5+10,mod=1004535809,G=3,Gi=334845270;
template <class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=-x;
}
template <class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n;
int fac[N],finv[N];
int bit,tot,rev[N];
int g[N],ginv[N],h[N];
int c[N];

inline void init(int len)
{
	bit=0;
	while((1<<bit)<(len<<1))bit++;
	tot=1<<bit;
	for(int i=0;i<tot;i++)
		rev[i]=(rev[i>>1]>>1)|((i&1)<<bit-1);
}
inline int adj(int x){return (x>=mod)?x-mod:x;}
inline int qpow(int x,int k)
{
	int res=1;
	while(k)
	{
		if(k&1)res=1ll*res*x%mod;
		x=1ll*x*x%mod;
		k>>=1;
	}
	return res;
}
inline void NTT(int *a,int inv)
{
	for(int i=0;i<tot;i++)
		if(rev[i]<i)swap(a[rev[i]],a[i]);
	for(int mid=1;mid<tot;mid<<=1)
	{
		int g=qpow(inv==1?G:Gi,(mod-1)/(mid<<1));
		for(int i=0;i<tot;i+=(mid<<1))
			for(int j=0,cur=1;j<mid;j++,cur=1ll*cur*g%mod)
			{
				int x=a[i+j],y=1ll*cur*a[i+j+mid]%mod;
				a[i+j]=adj(x+y),a[i+j+mid]=adj(x-y+mod);
			}
	}
}

void poly_mul(int *a,int *b,int n)
{
	init(n);
	NTT(a,1),NTT(b,1);
	for(int i=0;i<tot;i++)
		a[i]=1ll*a[i]*b[i]%mod;
	NTT(a,-1);
	int inv=qpow(tot,mod-2);
	for(int i=0;i<tot;i++)
		a[i]=adj(1ll*a[i]*inv%mod+mod);
}

void poly_inv(int *a,int *b,int len)
{
	if(len==1)
	{
		b[0]=qpow(a[0],mod-2);
		return ;
	}
	poly_inv(a,b,(len+1)>>1);
	init(len);
	for(int i=(len+1)>>1;i<tot;i++)b[i]=0;
	for(int i=0;i<tot;i++)
		c[i]=(i<len?a[i]:0);
	NTT(b,1),NTT(c,1);
	for(int i=0;i<tot;i++)
		b[i]=1ll*adj(2-1ll*b[i]*c[i]%mod+mod)*b[i]%mod;
	NTT(b,-1);
	int inv=qpow(tot,mod-2);
	for(int i=0;i<tot;i++)
		b[i]=adj(1ll*b[i]*inv%mod+mod);
	for(int i=len;i<tot;i++)b[i]=0;
}

int main()
{
	read(n);
	fac[0]=finv[0]=1;
	for(int i=1;i<=n;i++)
		fac[i]=1ll*fac[i-1]*i%mod,finv[i]=qpow(fac[i],mod-2);
	g[0]=1;
	for(int i=1;i<=n;i++)
	{
		int res=qpow(2,(1ll*i*(i-1)/2)%(mod-1));
		g[i]=1ll*res*finv[i]%mod;
		h[i]=1ll*res*finv[i-1]%mod;
	}
	n++;
	poly_inv(g,ginv,n);
	poly_mul(h,ginv,n);
	n--;
	printf("%d\n",1ll*h[n]*fac[n-1]%mod);
	return 0;
}