P4981 父子 （Cayley公式）

P4981 父子

分析：

• 这题是 $Cayley$ 公式的板子题

  $Cayley$ 公式介绍：

  • 用来求这样一个问题的：问 $n$ 个有标号点能组成多少棵不同的无根树
    $$ans=n^{n-2}$$

  证明见大佬博客题解 P4981 【父子】 - DPairの博客

• 再回到这题，这题显然是个有根树，寝室长为树根，$n$ 个人便有 $n$ 种情况

  故 $ans=n\ast n^{n-2}$

#include <bits/stdc++.h>
#define int long long 
using namespace std;

const int mo=1e9+9;
int ksm(int a,int b,int p=mo)
{
    int ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%p;
        a=a*a%p; b>>=1;
    }
    return ans;
}

signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        cout<<ksm(n,n-1)<<endl;
    }

    return 0;
}