题目传送门: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; }
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.
Great wordpress blog here.. It’s hard to find quality writing like yours these days. I really appreciate people like you! take care