[luogu]P4430 小猴打架 生成树Cayley定理

前言

https://www.luogu.com.cn/problem/P4430 树的尽头便是数论吗（QAQ）

思路

前置技能: Cayley定理： 不同的n节点带标号生成无根树的数量为 n n − 2 n^{n-2} nn−2

又因为题中不考虑前后顺序(也就是排列) 对于生成的树有(n-1)条边,所以 这题的公式如下:

( n − 1 ) ! ∗ n n − 2   m o d   9999991 (n-1) ! * n^{n-2} \bmod 9999991 (n−1)!∗nn−2mod9999991

CODE

#include 
using namespace std;
using ll = long long;
ll ans = 1;
int n;

void solve()
{
    cin>>n;
    for(int i=1;i