LUOGU P2290 [HNOI2004]树的计数(组合数，prufer序)

解题思路

　　\(prufer\)序，就是所有的不同的无根树，都可以转化为唯一的序列。做法就是每次从度数为\(1\)的点中选出一个字典序最小的，把这个点删掉，并把这个点相连的节点加入序列，直到只剩两个节点。然后这个东西有一个显然的性质就是所有点会在序列中出现这个点的度数\(-1\)次，这个性质有一个推论就是给你一棵树所有点的度数，你可以算出无根树不同形态的个数。公式为\(ans=\frac{(n-2)!}{\prod_{i=1}^{n}(deg[i]-1)!}\)。然后注意要质因数分解，否则中间会爆\(long long\)，还要特判一些东西。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int MAXN = 155;

typedef long long LL;

inline int rd(){

	int x=0,f=1;char ch=getchar();

	while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}

	while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

	return f?x:-x;

}

int n,deg[MAXN],num[MAXN],prime[MAXN],cnt,sum;

bool vis[MAXN];

LL ans=1;

void solve(int x,int k){

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

		while((x%prime[i]==0)) {num[i]+=k;x/=prime[i];}

		if(x==1) break;

	}

}

int main(){

	n=rd();

	if(n==1) {puts(rd()==0?"1":"0");return 0;}

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

		deg[i]=rd();sum+=deg[i];

		if(!deg[i]) {puts("0");return 0;}

		deg[i]--;

	}

	if(sum/2+1!=n) {puts("0");return 0;}

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

		if(!vis[i]) {prime[++cnt]=i;vis[i]=1;}

		for(int j=1;j<=cnt && i*prime[j]<=150;j++){

			vis[i*prime[j]]=1;

			if(!(i%prime[j])) break;

		}

	}

	for(int i=2;i<=n-2;i++) solve(i,1);

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

		if(deg[i]<=1) continue;

		for(int j=2;j<=deg[i];j++) solve(j,-1);

	}

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

		while(num[i]--) ans*=prime[i];

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

	return 0;

}

巴特西

LUOGU P2290 [HNOI2004]树的计数(组合数，prufer序)

解题思路

代码

最新文章

热门文章