UVa 1645 - Count(递推)

给出一个数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博客 ,格式可能有所偏差。