2021.07.18 P2290 树的计数（prufer序列、组合数学）

2021.07.18 P2290 树的计数（prufer序列、组合数学）

[P2290 HNOI2004]树的计数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

重点：

1.prufer序列

2.多重集的全排列公式

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

多重集的全排列 - Tekka - 博客园 (cnblogs.com)

3.排列组合优化算法及组合数与杨辉三角的关系

(4条消息) 杨辉三角与组合数_Bell的博客-CSDN博客_杨辉三角组合数公式

题意：

直接使用多重集的全排列公式，死算~

分析：

同上。

代码如下：

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

using namespace std;

#define int long long

const int N=160;

int n,a[N],sum,ans,f[N][N];

inline int read(){

	int s=0,w=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){

		if(ch=='-')w=-1;

		ch=getchar();

	}

	while(ch<='9'&&ch>='0'){

		s=s*10+ch-'0';

		ch=getchar();

	}

	return s*w;

}

signed main(){

	n=read();

	if(n==1){

		int c;

		c=read();

		if(c==0)cout<<"1";

		else cout<<"0";

		return 0;

	}

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

		f[i][0]=1;

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

		f[i][j]=f[i-1][j]+f[i-1][j-1];//,cout<<f[i][j]<<" ";

		//cout<<endl;//

	}

	//cout<<endl;//

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

		a[i]=read();

		if(!a[i]){

			cout<<"0";

			return 0;

		}

		--a[i];

		sum+=a[i];

	}

	if(sum!=n-2){

		cout<<"0";

		return 0;

	}

	sum=0,ans=1;

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

	ans*=f[n-2-sum][a[i]],sum+=a[i];

	cout<<ans;

	return 0;

}

2021.07.18 P2290 树的计数（prufer序列、组合数学）的相关教程结束。