解题报告-省赛F题

先来说一下prufer code,很多人做不出就是应为对他不了解,有根树和无根树都有prufer code ,产生的方法都差不多,f题是一颗无根树,因为他说vertex with degree zero or one is called leaf .以下都只说无根树

至以想进一步了解prufer可以做一下

http://acm.zju.edu.cn/show_problem.php?pid=1097

(prufer编码)和

http://acm.zju.edu.cn/show_problem.php?pid=1965

(prufer解码)

接下来说一下标号树的计数公式

N个节点的标号树有n^(n-2)种.这个公式很多地方都有,他的证明和prufer code 有很大的关系,应为标号树和prufer code是一一对应的(还有要说明一下zju产生的prufer code 的序列的长度是n-1的,而另外的一些资料是n-2的)

如果你做了1965的话,你就会发现需要用的的序列长度只要n-2

因为是一一对映,所以只要算出(用n个不同的元素,排成长度围n-2的总数,可以重复),只要用乘法原理就可以得到了,就是n^(n-2).

接下来说一下stirling数,如果没听过的话,就应好好学一下组合数学了,这个stirling最好去看下教材,他的一个最简单的应用就是(把n个不同的球放到m个无法区别的盒子里的种数(每个盒子至少有一个球))就是S(n,m)

1

1 1

1 3 1

1 7 6 1

和杨辉三角有点类似.

他的公式是S(n,m)=S(n-1,m-1)+S(n-1,m)*m;

现在来说f题吧

因为叶子的编号一定不会出现在prufer code 中,而非叶子一定出现在prufer code中,也就是说序列中一定恰好有n-k 个不同的元素, 刚才说了这个序列的长度是 n-2

下面来解决这个问题吧

第一步 ,从n个数中取出n-k个数,有C(n,n-k)种

第二步 设序列为a[1],a[2],a[3],......a[n-2]放到n-k个盒子里,有S(n-2,n-k)种

第三步 对n-k个盒子排序,有(n-k)!种

所以 答案是C(n,n-k)*S(n-2,n-k)*(n-k)!;

代码如下

#include<stdio.h>

#include<string.h>

int s[105][105],c[105][105],f[105];

int main()

{

int i,j,k;

// freopen("tree.in","r",stdin);

memset(s,0,sizeof(s));

memset(c,0,sizeof(c));

for(i=0;i<=100;i++)

for(j=0;j<=100;j++)

{

if(j==0 || j==i)c[i][j]=1;

else c[i][j]=(c[i-1][j-1]+c[i-1][j])%2007;

}

s[0][0]=1;

for(i=1;i<=100;i++)

for(j=1;j<=100;j++)

{

if(j==1 ||j==i)s[i][j]=1;

else s[i][j]=(s[i-1][j-1]+s[i-1][j]*j)%2007;

}

f[0]=1;

for(i=1;i<=100;i++)f[i]=(f[i-1]*i)%2007;

int n;

while(scanf("%d%d",&n,&k)!=EOF)

{

printf("%d\n",(c[n][n-k]*s[n-2][n-k]%2007)*f[n-k]%2007);

}

}