首页 > 其他 > 详细

test20200409 哈德曼的妖怪少女

时间:2020-04-09 21:04:37      阅读:66      评论:0      收藏:0      [点我收藏+]

拉格朗日反演

\[[x^n]F(x)=\frac{1}{n}[x^{n-1}](\frac{x}{F^{-1}(x)})^n \]

\[[x^n]G(F(x))=\frac{1}{n}[x^{n-1}]G‘(x)(\frac{x}{F^{-1}(x)}) \]

知道反函数可以\(O(n\log n)\)地求原函数的一项。

\[[x^n]F^{-1}(x)=\frac{1}{n}[x^{n-1}](\frac{x}{F(x)})^n \]

\[[x^n]G(F^{-1}(x))=\frac{1}{n}[x^{n-1}]G‘(x)(\frac{x}{F(x)}) \]

知道原函数可以\(O(n\log n)\)地求反函数的一项。

Prufer序列

考虑带标号有根树的指数型生成函数 \(F(x)\)

\[F(x)=x\exp(F(x))\x=\frac{F(x)}{\exp(F(x))} \]

那么我们就得到了 \(F(x)\) 的反函数 \(F^{-1}(x)\)

\[F^{-1}(x)=\frac{x}{\exp(x)} \]

运用拉格朗日反演,用反函数算原函数的\(n\)次方项。

\[[x^n]F(x)=\frac{1}{n}[x^{n-1}](\frac{x}{F^{-1}(x)})^{n}\=\frac{1}{n}[x^{n-1}]\exp(nx)\\frac{f_n}{n!}=\frac{1}{n}\frac{n^{n-1}}{(n-1)!}\f_n=n^{n-1} \]

所以\(n\)个点的有标号无根树的数量是\(n^{n-2}\)

连通块拼接

在一个\(s\)个点的图中,存在\(s?n\)条边,使图中形成了\(n\)个连通块,第\(i\)个连通块中有\(a_i\)个点。

现在我们需要再连接\(n?1\)条边,使该图变成一棵树。问连边的方案数。

题解

考虑构造Prufer序列,序列中的数字表示连通块编号。

若第\(k\)个连通块出现了\(i\)次,连边方案为\(a_k^i\),序列填空方案的分母为\(\frac{1}{i!}\)

所以生成函数为

\[(n-2)!\prod_{k=1}^n \sum_{i=0}^\infty a_k^i\frac{x^i}{i!}=(n-2)!\prod_{k=1}^na_k\exp(a_kx)\=(n-2)!\exp(sx)\prod_{k=1}^na_k \]

\[ans=[x^{n-2}](n-2)!\prod_{k=1}^na_k\exp(sx)\=s^{n-2}\prod_{k=1}^n a_k \]

哈德曼的奇怪少女

一个简单连通无向图是好的,当且仅当图中的每个极大边双连通分量的大小都在给定的集合\(S\)内。

给出集合\(S\),求有多少个\(n\)个点的好的无向图。两个无向图不同当且仅当存在一条边\((u,v)\)出现在其中一个无向图中,而不出现在另一个无向图中。

\(n\leq 10^5,\sum_{x\in S}x\leq 10^5\)

题解

对于一张简单连通图,将其所有的边双缩点后会得到一棵树。

容易发现这道题分为两部分:

  1. 对于所有\(i \in S\),求出\(b_i\)表示\(i\)个点的带标号无根边双的数量。

  2. 把所有的\(b_i\)拼成一棵无根树。

有根边双计数

\(B(x)\)为有根边双的指数型生成函数。

\(D(x)\)为有根连通图的指数型生成函数。

\[D(x)=B(x\exp(D(x))) \]

\(P(x)=x\exp(D(x))\)

\[D(x)=B(P(x))\D(P^{-1}(x))=B(x) \]

\[[x^n]B(x)=[x^n]D(P^{-1}(x))\=\frac{1}{n}{x^{n-1}}D‘(x)(\frac{x}{P(x)})^n \]

那么我们可以用多项式\(\ln\)\(\exp\)\(O(n \log n)\)的时间内求出所有我们需要的\(b_i\)

连通块拼接

接下来我们要把所有的\(b_i\)组合成一棵树。

考虑假设当前我们有\(m\)个连通块,第\(i\)个大小为\(a_i\),把这\(m\)个连通块拼成一棵树的方案数为\(n^{m?2}\prod a_i\)

\(\frac{\prod a_in}{n^2}\),每选一个大小为\(a\)连通块会多出\(a\cdot n\)的贡献。

那么我们令\(c_i = b_ii\cdot n\)\(C(x)\)\(c\)的生成函数,求出\([x^n]\exp(C(x))\)即可。

总复杂度\(O(n \log n)\)

\(B_s(x)\)好的有根边双的指数型生成函数。

\(D_s(x)\)好的有根连通图的指数型生成函数。

\[D_S(x)=B_S(x\exp(D_S(x)))\B_S^{-1}(D_S(x))=x\exp(D_S(x))\B_S^{-1}(x)=D_S^{-1}(x)\exp(x)\D_S^{-1}(x)=\frac{B_S^{-1}(x)}{\exp(x)} \]

问题在于这个\(B_S^{-1}(x)\)怎么求。它只有有限项系数非零,如果能有复杂度与这些项的次数的和相关的算法就好了。

CO int N=1<<18;
int omg[2][N],rev[N];
int fac[N],inv[N],ifac[N];

void NTT(poly&a,int dir){
	int lim=a.size(),len=log2(lim);
	for(int i=0;i<lim;++i) rev[i]=rev[i>>1]>>1|(i&1)<<(len-1);
	for(int i=0;i<lim;++i)if(i<rev[i]) swap(a[i],a[rev[i]]);
	for(int i=1;i<lim;i<<=1)
		for(int j=0;j<lim;j+=i<<1)for(int k=0;k<i;++k){
			int t=mul(omg[dir][N/(i<<1)*k],a[j+i+k]);
			a[j+i+k]=add(a[j+k],mod-t),a[j+k]=add(a[j+k],t);
		}
	if(dir==1){
		int ilim=fpow(lim,mod-2);
		for(int i=0;i<lim;++i) a[i]=mul(a[i],ilim);
	}
}
poly operator~(poly a){
	int n=a.size();
	poly b={fpow(a[0],mod-2)};
	if(n==1) return b;
	a.resize(1<<(int)ceil(log2(n)));
	for(int lim=2;lim<2*n;lim<<=1){
		poly c(a.begin(),a.begin()+lim);
		c.resize(lim<<1),NTT(c,0);
		b.resize(lim<<1),NTT(b,0);
		for(int i=0;i<lim<<1;++i) b[i]=mul(2+mod-mul(c[i],b[i]),b[i]);
		NTT(b,1),b.resize(lim);
	}
	return b.resize(n),b;
}
poly log(poly a){
	int n=a.size();
	poly b=~a;
	for(int i=0;i<n-1;++i) a[i]=mul(a[i+1],i+1);
	a.resize(n-1);
	int lim=1<<(int)ceil(log2(2*n-2));
	a.resize(lim),NTT(a,0);
	b.resize(lim),NTT(b,0);
	for(int i=0;i<lim;++i) a[i]=mul(a[i],b[i]);
	NTT(a,1),a.resize(n);
	for(int i=n-1;i>=1;--i) a[i]=mul(a[i-1],inv[i]);
	return a[0]=0,a;
}
poly exp(poly a){
	int n=a.size();
	poly b={1};
	if(n==1) return b;
	a.resize(1<<(int)ceil(log2(n)));
	for(int lim=2;lim<2*n;lim<<=1){
		b.resize(lim);poly c=log(b);
		c[0]=add(1+a[0],mod-c[0]);
		for(int i=1;i<lim;++i) c[i]=add(a[i],mod-c[i]);
		c.resize(lim<<1),NTT(c,0);
		b.resize(lim<<1),NTT(b,0);
		for(int i=0;i<lim<<1;++i) b[i]=mul(c[i],b[i]);
		NTT(b,1),b.resize(lim);
	}
	return b.resize(n),b;
}
poly operator*(poly a,poly b){
	int n=a.size()+b.size()-1,lim=1<<(int)ceil(log2(n));
	a.resize(lim),NTT(a,0);
	b.resize(lim),NTT(b,0);
	for(int i=0;i<lim;++i) a[i]=mul(a[i],b[i]);
	NTT(a,1),a.resize(n);
	return a;
}

int solve(int n){
	poly f(n+1);
	for(int i=0;i<=n;++i) f[i]=mul(fpow(2,(int64)i*(i-1)/2%(mod-1)),ifac[i]);
	f=log(f);
	for(int i=0;i<=n;++i) f[i]=mul(f[i],i);
	poly g=f;
	for(int i=0;i<=n;++i) g[i]=mul(g[i],mod-n);
	for(int i=0;i<n;++i) f[i]=mul(f[i+1],i+1);
	f.resize(n);
	int ans=mul((f*exp(g))[n-1],inv[n]);
	ans=mul(ans,fac[n-1]);
	return ans;
}
int main(){
	freopen("koishi.in","r",stdin),freopen("koishi.out","w",stdout);
	omg[0][0]=1,omg[0][1]=fpow(3,(mod-1)/N);
	omg[1][0]=1,omg[1][1]=fpow(omg[0][1],mod-2);
	fac[0]=fac[1]=1;
	inv[0]=inv[1]=1;
	ifac[0]=ifac[1]=1;
	for(int i=2;i<N;++i){
		omg[0][i]=mul(omg[0][i-1],omg[0][1]);
		omg[1][i]=mul(omg[1][i-1],omg[1][1]);
		fac[i]=mul(fac[i-1],i);
		inv[i]=mul(mod-mod/i,inv[mod%i]);
		ifac[i]=mul(ifac[i-1],inv[i]);
	}
	int n=read<int>();
	poly f(n+1);
	for(int m=read<int>();m--;){
		int x=read<int>();
		if(x>n) continue;
		f[x]=mul(solve(x),mul(x,n));
	}
	for(int i=0;i<=n;++i) f[i]=mul(f[i],ifac[i]);
	int ans=mul(exp(f)[n],fac[n]);
	ans=mul(ans,mul(inv[n],inv[n]));
	printf("%d\n",ans);
	return 0;
}

test20200409 哈德曼的妖怪少女

原文:https://www.cnblogs.com/autoint/p/12669171.html

(1)
(1)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!