Chrysanthemum's Blog

Description

Input

Output

Sample Input

Sample Output

HINT

请原谅我刷水，。

首先根据prufer序列的性质，互不相同的树的个数有n^n-2个，然后对于每一棵树，打架的顺序有（n-1）！种，两者相乘，即为本题答案。。。

代码：

#include<cstdio>
#define mod 9999991
using namespace std;
typedef long long ll;
int n;
ll ans;
ll ksm(ll x,int y){ll ans=1;while (y){if (y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;}
int main()
{
	scanf("%d",&n);
	ans=ksm(n,n-2);
	for (int i=1;i<n;i++) ans=ans*(ll)i%mod;
	printf("%lld\n",ans);
}

Description

Input

Output

Sample Input

Sample Output

prufer序列。。。一个非常鬼畜的东西。

是这样的，给定一棵树，他的prufer序列就是：

每一次找到编号最小的叶子节点，然后将与这个节点相连的点的编号加入序列，然后把这个叶子节点删除，直到最终剩下两个点为止，

比如这样一棵树

     1

    /  \

   2    5

  /  \    \

 6    3    4

首先找到3，2进入序列，此时序列为{2}

找到4,5进入序列，此时序列为{2,5}

找到5,1进入序列，此时序列为{2,5,1}

找到1,2进入序列，此时序列为{2,5,1,2}

还剩2,6，退出。

可以证明，prufer序列的长度为n-2，且每个节点在序列中出现次数，恰为度-1。

这样就可以做这道题了。就变成一道排列组合题了。答案为：(n-2)!/((d1-1)!(d2-1)!……(dn-1)!)

注意点：

一、注意判无解的情况，n不为1但有一个点的度为0，或者点的度之和不等于n-2

二、尽管ans可以用long long，但中间过程肯定会爆，因此，只要质因数分解就可以了。

代码：

#include<cstdio>
using namespace std;
typedef long long ll;
int n,sum,f[210],d[210];
ll ans;
void add(int x,int val)
{
	for (int i=2;i*i<=x;i++)
	if (x%i==0) while (x%i==0){x/=i;f[i]+=val;}
	if (x!=1)f[x]+=val;
}
ll ksm(ll x,int y)
{
	ll ans=1;
	while (y)
	{
		if (y&1) ans*=x;
		x*=x;
		y>>=1;
	}
	return ans;
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&d[i]);
		if ((!d[i])&&n!=1){printf("0\n");return 0;}
	}
	for (int i=1;i<=n;i++)
		sum+=d[i]-1;
	if (sum!=n-2){printf("0\n");return 0;}
	if (n==1&&d[1]==0){printf("1\n");return 0;}
	for (int i=2;i<=n-2;i++)
		add(i,1);
	for (int i=1;i<=n;i++)
		for (int j=2;j<=d[i]-1;j++)
			add(j,-1);
	ans=1;
	for (int i=1;i<=n;i++)
	if (f[i]) ans*=ksm(i,f[i]);
	printf("%lld\n",ans);
}