2021.07.19 P2624 明明的烦恼（prufer序列，为什么杨辉三角我没搞出来？）

2021.07.19 P2624 明明的烦恼（prufer序列，为什么杨辉三角我没搞出来？）

[P2624 HNOI2008]明明的烦恼 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

重点：

1.prufer序列

2.组合数学

题意：

n个点，有部分点已经确定度数，有的随意，问有多少棵树满足已知度数要求。

分析：

还能分析个锤子出来，prufer序列啊，记得开高精，杨辉三角被我玩儿废了，搞不定，我太菜了。

设已知度数的点有k个，总度数-k为s，一共有n个点。

则这k个点能形成的树的个数为

\[\frac{s!}{\prod_{i=1}^{k}{(a_i-1)!}}
\]

因为是n-2个点中随意选s个点（暂时把这些所有的点看成不同的点），所以还要再乘上下面一坨东东

\[C_{n-2}^{s}
\]

最后还要乘上其它n-2-k个数的随机排列

\[(n-k)^{n-2-s}
\]

所以总公式为

\[C_{n-2}^{s}*\frac{s!}{\prod_{i=1}^{k}{(a_i-1)!}}*(n-k)^{n-2-s}
\]

代码如下：

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std;

int n,cnt,a[1010],sum,tot;

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;

}

struct node{

	int num[10100],len;

	node(){

		memset(num,0,sizeof(num));

		len=1;

	}

	node operator *(const int &x)const{

		node ans;

		ans.len=len+6;

		for(int i=1;i<=len;i++)ans.num[i]+=num[i]*x;

		for(int i=1;i<ans.len;i++){

			if(ans.num[i]>9){

				ans.num[i+1]+=ans.num[i]/10;

				ans.num[i]%=10;

			}

		}

		while(!ans.num[--ans.len]);

		return ans;

	}

	node operator /(const int &x)const{

		node ans;

		ans=*this;

		++ans.len;

		for(int i=ans.len;i;i--){

			ans.num[i-1]+=ans.num[i]%x*10;

			ans.num[i]/=x;

		}

		while(!ans.num[--ans.len]);

		return ans;

	}

}ans;

int main(){

	n=read();

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

		a[i]=read();

		if(!a[i])return cout<<"0",0;

		else if(a[i]!=-1)sum+=a[i]-1,++cnt;

	}

	if(sum>2*n-2)return cout<<"0",0;

	ans.num[1]=1;

	for(int i=n-1-sum;i<n-1;i++)ans=ans*i;

	for(int i=1;i<=n-2-sum;i++)ans=ans*(n-cnt);

	for(int i=1;i<=n;i++)for(int j=2;j<=a[i]-1;j++)

	ans=ans/j;

	for(int i=ans.len;i;i--)cout<<ans.num[i];

	return 0;

}

2021.07.19 P2624 明明的烦恼（prufer序列，为什么杨辉三角我没搞出来？）的相关教程结束。