BZOJ3321 生成树Stcnt

2015.01.08 10:51 Thu| 11 visits oi_2015| 2015_刷题日常| Text

Solution

由矩阵树定理打表找规律,得 $ans_{n, k} = n^{n-2} * (n-1)^{(k-1)n} * k^{kn-2}$ 。QY大神可是推导出来的这个公式 orz orz。

这里给出利用按照定理 $\mathcal O(n^3)$ 暴力得出如下可爱的表【经过许久的分解质因数+化简得 T^T】~

于是简单写一个快速幂就好了~

Code

#include <bits/stdc++.h>
#define mod 1000000007

using namespace std;

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

int main()
{
  long long n, k;
  cin >> n >> k;
  cout << power(n, n - 2) * power(n - 1, (k - 1) * n) % mod *
          power(k, k * n - 2) %mod << endl;
}