[luogu] P4981 父子 Cayley定理

前言

https://www.luogu.com.cn/problem/P4981

我是來做最小生成樹的QAQ(怎麼下一題又是Cayley定理)

思路

看完題目不難發現

就是讓我們求 n個節點的有根樹 有多少個形态

已知Cayley定理是求無根樹

是以對于每一個無根樹 我們都有n種選根 方案

是以這題的公式就是:

n n − 1   m o d   1 e 9 + 9 n^{n-1} \bmod 1e9+9 nn−1mod1e9+9

因為有t組 選擇用qmi

CODE

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll ans = 1;
const int mod  = 1e9+9;
int n;
int  qmi(ll a, ll b)
{
    a %= mod;
    ll res = 1;
    while (b > 0)
    {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

void solve()
{
    int n;
    cin>>n;
    cout<<qmi(n,n-1)<<endl;
   // cout<<ans<<endl;
}
int main()
{
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t -- )
    solve();

    return 0;
}