P2817 宋荣子的城堡

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)

 #include<iostream>

 #include<cstdio>

 #include<queue>

 #include<algorithm>

 #include<cmath>

 #include<ctime>

 #include<cstring>

 #define mod 1000000007

 #define inf 2147483647

 #define For(i,a,b) for(register long long i=a;i<=b;i++)

 #define p(a) putchar(a)

 #define g() getchar()

 //by war

 //2017.10.19

 using namespace std;

 long long n,k;

 void in(long long &x)

 {

     long long y=;

     char c=g();x=;

     while(c<''||c>'')

     {

     if(c=='-')

     y=-;

     c=g();

     }

     while(c<=''&&c>='')x=x*+c-'',c=g();

     x*=y;

 }

 void o(long long x)

 {

     if(x<)

     {

         p('-');

         x=-x;

     }

     if(x>)o(x/);

     p(x%+'');

 }

 long long POW(long long a,long long b)

 {

     a%=mod;

     if(b==)

     return ;

     while(b%==)

     {

         a=(a*a)%mod;

         b>>=;

     }

     long long r=;

     while(b>)

     {

         if(b%==)

         r=(r*a)%mod;

         a=(a*a)%mod;

         b>>=;

     }

     return r;

 }

 int main()

 {

     in(n),in(k);

 //    n%=mod;

     o((POW(k,k-)*POW(n-k,n-k))%mod);

      return ;

 }

巴特西

P2817 宋荣子的城堡

最新文章

热门文章