UVA10843 Anne‘s game 题解

UVA10843 Anne’s game 题解

结论题。

解法

首先引入 Prüfer 序列。Prüfer 序列是一种将有标号的树映射到整数序列上的方法。本题用到的是将有标号无根树映射到整数序列的方法，这个映射是一一到上的（即双射）。

对于每个 n n n 个节点的有标号无根树，我们都可以使用一个长度为 n − 2 n-2 n−2 的每个元素都 ∈ [ 1 , n ] \in[1,n] ∈[1,n] 的 Prüfer 序列来表示。

从树到 Prüfer 序列：每次选择一个编号最小的度数为 1 1 1 的节点并删掉它，在序列中压入与这个节点相连的节点。该过程重复 n − 2 n-2 n−2 次。

从 Prüfer 序列到树：首先我们可以很容易地得到所有点的度数。我们枚举 Prüfer 中的点，再选择一个度数为 1 1 1 的编号最小的点，把两个点连起来，并且把两个点的度数都减 1 1 1。重复 n − 2 n-2 n−2 次后会剩下两个点，把这两个点连起来就好。

根据上述两个过程，显然 Prüfer 序列与有标号无根树的个数之间是一一到上映射（即双射）。

因为 Prüfer 序列的元素都 ∈ [ 1 , n ] \in[1,n] ∈[1,n]，且长度是 n − 2 n-2 n−2，所以共有 n n − 2 n^{n-2} nn−2 个有 n n n 个点的有标号无根树。

代码中特殊注意一下有 1 1 1 个点的有标号无根树个数为 1 1 1。

代码

#include<bits/stdc++.h>
namespace fast_IO
{
	/**
	 * fast IO
	*/
};
using namespace fast_IO;
#define int long long
int t,n;
const int p=2000000011;
inline int ksm(int a,int b)
{
	if(b<=0) return 1;
	int ret=1;
	while(b)
	{
		if(b&1) ret=ret*a%p,b--;
		a=a*a%p,b>>=1;
	}
	return ret;
}
signed main()
{
	in>>t;
	for(int i=1;i<=t;i++) in>>n,out<<"Case #"<<i<<": "<<ksm(n,n-2)<<'\n';
	fwrite(Ouf,1,p3-Ouf,stdout),fflush(stdout);
	return 0;
}