国际大学生程序设计竞赛例题_4,6树

1,题意:n个节点,每个节点都有编号.k(k>=2)个叶子,可以组成多少这样的树.
辅助方法:Prufer Code,选出标号最小的叶子点,删除,输出它的父亲节点编号,直到剩余两个节点.
得到一个n-2的序列,就是Prufer码,可以证明其和树是一一对应的.问题转化为先从n个节点选k个作为叶子,剩余的n-k个符号扩展为n-2长度的序列,即是对应的一种的方案.
结果:对2007取模
2,实现代码:

#include <iostream>
using namespace std;

const int MAX=105;
const int m=2007;//取模

int c[MAX][MAX]; //c[i][j]表示i个数取j个的组合数
//利用动态规划求:c[i][j]=c[i-1][j](没有用第j个)+c[i-1][j-1](用到了第j个)
int g[MAX][MAX];//g[i][j]:表示j个字符构造长为i的方案数(所有字符都要用到)
//g[i][j]=j*g[i-1][j]+j*g[i-1][j-1]
void init()
{
    memset(c,0,sizeof(c));
    for(int i=0;i<=100;i++)
        for(int j=0;j<=i;j++)
        {
            if(j==0) c[i][j]=1;
            else c[i][j]=(c[i-1][j]+c[i-1][j-1])%m;
        }
    memset(g,0,sizeof(g));
    g[0][0]=1;
    for(int i=1;i<=100;i++)
        for(int j=1;j<=i;j++)
            g[i][j]=(j*g[i-1][j]+j*g[i-1][j-1])%m;
}

int main()
{
    //freopen("4.6.in","r",stdin);
    int n,k;//节点数和叶子数
    init();
    while(cin>>n>>k)
    {
        //一个节点只有一种方案
        if(n==1) cout<<"1"<<endl;
        else cout<<(c[n][k]*g[n-2][n-k])%m<<endl;
    }
    return 0;
}