BZOJ1430 小猴打架

2015.01.03 19:50 Sat| 0 visits oi_2015| 2015_刷题日常| Text

Solution

Prufer编码解决这道题的思路很简单 = =。Prufer编码即为一个和树一一对应的序列,n节点的树对应的Prufer序列长度为n-2。于是可以推得Cayley公式:一个n个点的完全图可以得到 $n^{n-2}$ 棵生成树。于是这一道题就被简简单单地解决了,思考复杂度 $\mathcal O(1)$ 。

当然,还可以用 Matrices Tree 定理来尝试推导,今天大神讲的时候好像没有听懂?总之是一件很麻烦的事情。。。

Code

#include <bits/stdc++.h>
using namespace std;
#define mod 9999991

long long n, f=1;

long long power(long long a,long long b,long long c)
{
    long long re=1; a%=c;
    while(b)
    {
        if(b&1) re=(re*a)%c;
        a=(a*a)%c; b>>=1;
    }
    return re;
}

int main()
{
    cin >> n;
    for(long long i=1; i<n; i++) f = f * i % mod;
    cout << power(n, n-2, mod) * f % mod<< endl;
    return 0;
}