[洛谷 4981]父子

题目链接

https://www.luogu.org/problem/P4981

题解

根据 prufer 序列的结论，我们可以知道 \(n\) 个节点的无根树个数为 \(n^{n-2}\)。

现在我们要求的是有根树的数量。因为每个节点都可以设置为根，答案显然是 \(n*n^{n-2}=n^{n-1}\)。

#include <iostream>
#include <algorithm>
#define MOD 1000000009
using namespace std;
long long fpow(long long a,long long b)
{
 long long ans=1;
 while(b)
 {
  if(b&1)ans=ans*a%MOD;
  a=a*a%MOD;
  b>>=1;
 }
 return ans;
}
int main()
{
 int t;
 cin>>t;
 while(t--)
 {
  int n;
  cin>>n;
  cout<<fpow(n,n-1)<<endl;
 }
 return 0;
}