UVa 1645 - Count（递推）

发表于 分类于 ， Disqus：

给出一个数n，求n个结点的树有多少种结构满足每个结点的子结点数相同。

n结点树，除去根结点，有n-1个结点，根结点的每棵子树需要完全相同，所以根结点的子树个数k，满足(n-1)%k==0。然后就可以递推打表了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
using namespace std;
const int maxn=1010,mod=1000000007;
int a[maxn]={0,1},t,n;
void pre(){
    for(int i=1;i<maxn;++i)
        for(int j=1;j<i;++j){
            if((i-1)%j) continue;
            a[i]+=a[j];
            a[i]%=mod;
        }
    return;
}
int main(){
    pre();
    while(cin>>n)
        cout<<"Case "<<++t<<": "<<a[n]<<endl;
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **