P4981 父子 Cayley公式-白红宇

P4981 父子 Cayley公式

阅读量：4991 次

发布时间：2019-06-12

本文共 1054 字，大约阅读时间需要 3 分钟。

$CayleyCayley公式的定义是这样的，对于n个不同的节点，能够组成的无根树（原来是无向连通图或者是有标志节点的树）的种数是n^（n-2）种。（这里让大家好理解一点，就写成了无根树，其实应该是一样的概念）$

那么我们的初步问题就解决了，接下来就是解决无根树和有根树之间的转换。

但是转换很难吗？把有根树转换成根节点有 $nn种情况的无根树，也就是n^（n-2） * n，化简就是n^（n-1）。答案也就是这个玩意了。$

因为这道题，

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                #include 
                 
                  #include 
                  
                   #define LL long long#define ULL unsigned long long#define rep(i,j,k) for(int i=j;i<=k;i++)#define dep(i,j,k) for(int i=k;i>=j;i--)#define INF 0x3f3f3f3f#define mem(i,j) memset(i,j,sizeof(i))#define make(i,j) make_pair(i,j)#define pb push_backusing namespace std;const int mod = 1e9 + 9;LL ksm(LL a, LL b) { LL ans = 1; while(b) { if(b & 1) ans = ans * a % mod; a = a * a % mod; b >>= 1; } return ans;}int main() { int n, t; scanf("%d", &t); while(t--) { scanf("%d", &n); cout << ksm(1LL * n, 1LL * ( n - 1)) <

View Code

转载于:https://www.cnblogs.com/Willems/p/11016727.html

你可能感兴趣的文章

Android系统源码下载及使用（Android 14到19源码）