父子【题解】

· · 个人记录

$\ \ \ \ \ \ \ $很明显可以看出，此题为结论题。 $\ \ \ \ \ \ \ $本题主要可以通过找规律得到答案……多画几组，便可以得到我们需要求的答案是： ## $$n^{n-1}$$ $\ \ \ \ \ \ \ $下面我们解释一下为什么： ------------ $\ \ \ \ \ \ \ $题目要求很明显，询问的是生成树个数，但是因为又向，所以求的具体是一个又向完全图内，生成树形图的个数。 $\ \ \ \ \ \ \ $我们不妨先把有向这个条件忽略一下，先考虑一下一个无向完全图的生成树个数。 $\ \ \ \ \ \ \ $已知每一棵树对应一个$\rm \ Prüfer\ $编码，$\rm Prüfer\ $编码中每一个数出现的次数为$(n-1)$，且$\rm \ Prüfer\ $编码的长度为$(n-2)$，完全图中每一个节点的度数为$(n-2)$，所以每一个$\rm \ Prüfer\ $编码的元素都有$\ n\ $种可能，所以答案为$n^{n-2}$。 $\ \ \ \ \ \ \ $此即为$\rm \ Cayley\ $公式，这里简单证明一下，有兴趣的可以在网上找相关证明。 ### $\ \ \ \ \ \ \ $所以我们现在知道，对于一个$\ n\ $个点无向完全图，生成树个数为 # $$n^{n-2}$$ $\ \ \ \ \ \ \ $那么加上有向的条件呢？ $\ \ \ \ \ \ \ $注意这里的无向完全图生成树，是没有根的。当一棵树有根的时候，我们就可以把它自然地转换成一棵树形图，这是一一对应的。对于任何一棵生成树，我们都有$\ n\ $个节点。所以就有$\ n\ $种树根。那么我们的答案就应该为： ## $$n^{n-2}\times n$$ $\ \ \ \ \ \ \ $既: ## $$n^{n-1}$$ ------------ 下面给出标程代码 $: 
#include<cstdio>
using namespace std;
typedef long long ll;
const int mod=1e9+9;
int n;
inline int read() {
    int x=0,p=1;
    char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-1') p=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*p;
}
ll all(ll a,int b) {
    ll ret=1;
    while(b) {
        if(b&1) ret=ret*a%mod;
        a=a*a%mod;b>>=1;
    }
    return ret;
}
int main() {
    int t=read();
    while(t--) {
        n=read();
        printf("%d\n",all(n,n-1));
    }
    return 0;
}

如果对本题还有什么疑问或者更好的做法，欢迎直接私信写题解的：@Althen·Way·Satan，他的邮箱[email protected]