【BZOJ 1430】小猴打架

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1430

首先,根据Cayley公式可以得到prufer序列和生成树一一对应
于是生成树的个数就有n^(n-2)个
另外,他求的还是排列数,所以还要乘上(n-1)条边的排列

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

const int MOD = 9999991;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

int main(){
	int n = read(), vout = 1;
	for (int i=1;i<=n-2;i++) {
		vout = (LL)vout * n % MOD;
	}
	for (int i=n-1;i;i--) {
		vout = (LL)vout * i % MOD;
	}
	cout<<vout<<endl;
	return 0;
}

2 thoughts to “【BZOJ 1430】小猴打架”

  1. I’m not sure the place you’re getting your info, but good topic. I must spend a while finding out more or figuring out more. Thanks for excellent information I was searching for this information for my mission.

Leave a Reply

Your email address will not be published. Required fields are marked *