明明的烦恼

自从明明学了树的结构,就对奇怪的树产生了兴趣...... 给出标号为1到N的点,以及某些点最终的度数,允许在任意两点间连线,可产生多少棵度数满足要求的树?

第一行为N(0<N<=1000),接下来N行,第i+1行给出第i个节点的度数Di,如果对度数不要求,则输入-1

分析

https://www.cnblogs.com/chenxiaoran666/p/prufer.html

https://blog.csdn.net/jeremygjy/article/details/50625228

首先我们根据prufer数列可以知道任意一棵无根树可以表示为任意一个长度为\(n−2\)的串并且有以下的性质任意一点的度为\(d_i\)那么该数字将会在数列中出现\(d_i−1\)次，那么我们可以知道该数列的总长度就是\(sum=\sum_{i=1}^n{d_i-1}\)当然前提是\(n\)个度数全部已知，那么我们已经知道了\(n\)个点的度数，我们可以构造出多少不同的prufer数列呢可以发现答案就是

\[\frac{(n-2)!}{\prod_{i=1}^n(d_i-1)!}
\]

但是我们现在并不知道这么多，我们现在已知的有\(cnt\)个，那么我们未知的有\(n−cnt\)个，那么我们如果不管不知道的，但是现在有\(n−2\)个空位所以答案是

\[C_{n-2}^{sum}\frac{sum!}{\prod_{i=1}^n(d_i-1)!}
\]

但是现在我们还有\((n−cnt)\)个未知那么我们的答案就是

\[C_{n-2}^{sum}\frac{sum!}{\prod_{i=1}^n(d_i-1)!}\times (n-cnt)^{n-2-sum}
\]

那么我们化简可以得到

\[\frac{(n-2)!}{sum!(n-2-sum)!}\frac{sum!}{\prod_{i=1}^n(d_i-1)!}\times (n-cnt)^{n-2-sum} \\
\frac{(n-2)!}{(n-2-sum)!\prod_{i=1}^n(d_i-1)!}\times (n-cnt)^{n-2-sum}
\]

因为\(n−2\)还是比较大所以靠分解质因数来解决高精度的问题。

高精度……引起了我SCOI2019不愉快的回忆。

co int N=1e3+1;

int p[N],num[N],n,d[N],cnt;

void init(){

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

		if(!p[i]) p[++p[0]]=i;

		for(int j=1;j<=p[0]&&p[j]*i<=n;++j){

			p[p[j]*i]=1;

			if(i%p[j]==0) break;

		}

	}

}

void decomp(int n,int f){

	for(int i=1;i<=p[0]&&p[i]<=n;++i)

		for(int j=n;j>=p[i];j/=p[i]) num[i]+=j/p[i]*f;

}

co int mod=1e6;

int ans[N]={1},len=1;

void mul(int n){

	for(int i=0;i<len;++i) ans[i]*=n;

	for(int i=0;i<len;++i)if(ans[i]>=mod)

		ans[i+1]+=ans[i]/mod,ans[i]%=mod;

	if(ans[len]) ++len;

}

int main(){

	if((read(n))==1) return puts(read<int>()<=0?"1":"0"),0;

	init();

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

		if(read(d[i])==-1) continue;

		++cnt;

		if(d[i]<=0&&d[i]>=n) return puts("0"),0;

		if(d[i]!=-1) d[0]+=(d[i]-=1);

	}

	if(d[0]>n-2) return puts("0"),0;

	decomp(n-2,1),decomp(n-2-d[0],-1);

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

		if(d[i]!=-1) decomp(d[i],-1);

	for(int i=1;i<=p[0];++i)

		while(num[i]--) mul(p[i]);

	for(int i=n-2-d[0];i;--i) mul(n-cnt);

	printf("%d",ans[len-1]);

	for(int i=len-2;i>=0;--i) printf("%06d",ans[i]);

	return 0;

}

无聊的水题

DLS 喜欢上树。但是他并不想把一道数据结构题出到树上，他喜欢计 Tree。

这一天，他想自己造一棵树，他手头有 N 个树的节点，标号为1~N，他会在它们之间连边，我们定义两颗树不同，当且仅当一对节点在一棵树中有连边，另一棵树中没有连边。

但他不喜欢一棵太多分叉的树，于是他想让这棵树的节点中最大的度数为 M。

DLS 由于不太擅长理科，所以希望你帮他计算有多少棵这样的树。答案对 998244353 取模。

2≤N,M≤5⋅10⁴

题解

Prufer序列+生成函数。

最大的度数为 M 可以容斥。显然求的是

\[\left(\sum_{i=0}^{M-1}\frac{x^i}{i!}\right)^n-\left(\sum_{i=0}^{M-2}\frac{x^i}{i!}\right)^n
\]

使用多项式exp即可做到 \(O(n \log n)\)。

CO int N=131072;

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(1,fpow(a[0],mod-2));

	if(n==1) return b;

	int lim=2;

	for(;lim<n;lim<<=1){

		poly a1(a.begin(),a.begin()+lim);

		a1.resize(lim<<1),NTT(a1,0);

		b.resize(lim<<1),NTT(b,0);

		for(int i=0;i<lim<<1;++i) b[i]=mul(2+mod-mul(a1[i],b[i]),b[i]);

		NTT(b,1),b.resize(lim);

	}

	a.resize(lim<<1),NTT(a,0);

	b.resize(lim<<1),NTT(b,0);

	for(int i=0;i<lim<<1;++i) b[i]=mul(2+mod-mul(a[i],b[i]),b[i]);

	NTT(b,1),b.resize(n);

	return b;

}

poly log(poly a){

	int n=a.size();

	poly b=~a;

	a.resize(n-1);

	for(int i=0;i<n-1;++i) a[i]=mul(a[i+1],i+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,1); // a[0]=0

	if(n==1) return b;

	int lim=2;

	for(;lim<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(b[i],c[i]);

		NTT(b,1),b.resize(lim);

	}

	b.resize(lim);poly c=log(b);

	c[0]=add(1+a[0],mod-c[0]);

	for(int i=1;i<n;++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(b[i],c[i]);

	NTT(b,1),b.resize(n);

	return b;

}

int main(){

	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);

	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[0]=1;

	for(int i=1;i<N;++i) fac[i]=mul(fac[i-1],i);

	inv[0]=inv[1]=1;

	for(int i=2;i<N;++i) inv[i]=mul(mod-mod/i,inv[mod%i]);

	ifac[0]=1;

	for(int i=1;i<N;++i) ifac[i]=mul(ifac[i-1],inv[i]);

	int n=read<int>(),m=read<int>();

	poly a(ifac,ifac+m);

	a.resize(n-1),a=log(a);

	for(int i=0;i<n-1;++i) a[i]=mul(a[i],n);

	int ans=exp(a)[n-2];

	a.assign(ifac,ifac+m-1);

	a.resize(n-1),a=log(a);

	for(int i=0;i<n-1;++i) a[i]=mul(a[i],n);

	ans=add(ans,mod-exp(a)[n-2]);

	ans=mul(ans,fac[n-2]);

	printf("%d\n",ans);

	return 0;

}

巴特西

HNOI2004 树的计数和 HNOI2008 明明的烦恼

明明的烦恼

分析

无聊的水题

题解

最新文章

热门文章

巴特西

HNOI2004 树的计数 和 HNOI2008 明明的烦恼

明明的烦恼

分析

无聊的水题

题解

最新文章

热门文章

HNOI2004 树的计数和 HNOI2008 明明的烦恼