P2817 宋榮子的城堡
一道找規律的題，現在深入追究發現了有趣的東西。
1 1
2 2
3 9
4 64
顯然k^(k-1) 在日照的時候也推出來了。
3 9今天推錯了，要列出所有的情況，然后再選，否則會漏掉。
答案是(k^(k-1)) * ((n-k)^(n-k))
對了，我卡速米一直打的是錯的。要對指數為0的情況特判，不然會死循環。

現在，告訴我，why?

cayley定理（凱萊定理）
對于有n個節點，生成樹的方案有多少種?
答案是n^(n-2)
推導過程如下:
k表示現在有多少子樹
顯然初始時，k==n
現在從n個節點中任選1個，有C(n 1)種可能，再從不包含這個節點的子樹中選1個子樹和這個節點連起來，有C(k-1 1),然后子樹減少一個。重復這個過程直到，子樹只剩1個，乘法原理，(n^(n-1))*(n-1)!。
假定每次都是（從n個節點中任選1個）選的同一個，并把它設成根，想象一下，對于同一棵樹這就考慮了每個節點是根的情況。
有n-1條邊，不考慮加進來的順序，所以再除（n-1）!,現在成了n^(n-1)，在一棵樹中，根節點是哪個都無所謂，再除n，就成了
n^(n-2)。

但是對于這個題而言，可以假定1連向的點為根節點，實際上把它的每個點當成根節點都會形成新的方案，所以再*k
故答案 k^(k-1)

?

1 #include<iostream> 2 #include<cstdio> 3 #include<queue> 4 #include<algorithm> 5 #include<cmath> 6 #include<ctime> 7 #include<cstring> 8 #define mod 1000000007 9 #define inf 2147483647 10 #define For(i,a,b) for(register long long i=a;i<=b;i++) 11 #define p(a) putchar(a) 12 #define g() getchar() 13 //by war 14 //2017.10.19 15 using namespace std; 16 long long n,k; 17 void in(long long &x) 18 { 19 long long y=1; 20 char c=g();x=0; 21 while(c<'0'||c>'9') 22 { 23 if(c=='-') 24 y=-1; 25 c=g(); 26 } 27 while(c<='9'&&c>='0')x=x*10+c-'0',c=g(); 28 x*=y; 29 } 30 void o(long long x) 31 { 32 if(x<0) 33 { 34 p('-'); 35 x=-x; 36 } 37 if(x>9)o(x/10); 38 p(x%10+'0'); 39 } 40 41 long long POW(long long a,long long b) 42 { 43 a%=mod; 44 if(b==0) 45 return 1; 46 while(b%2==0) 47 { 48 a=(a*a)%mod; 49 b>>=1; 50 } 51 long long r=1; 52 while(b>0) 53 { 54 if(b%2==1) 55 r=(r*a)%mod; 56 a=(a*a)%mod; 57 b>>=1; 58 } 59 return r; 60 } 61 62 int main() 63 { 64 in(n),in(k); 65 // n%=mod; 66 o((POW(k,k-1)*POW(n-k,n-k))%mod); 67 return 0; 68 } View Code

?

轉載于:https://www.cnblogs.com/war1111/p/7695151.html

總結

以上是生活随笔為你收集整理的P2817 宋荣子的城堡的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。