题目:题目链接
题目大意:给你N个节点,求用这N个节点组成的轴对称的异构的树的数量。
思路:
1:n=1时,只有一颗;
2:n=2时,也只有一颗;
3:n=3时,有两颗
4:关于根节点那一个轴对称,则根节点下一定是m颗都含有k个节点的树,而且m*k=n-1(除去根节点);即n个节点组成对称树的数量等于1....n-1中,能被n-1整除的数的节点数的对称的树的总和。
#include <iostream> #include <cstdio> #include <string> #include <string.h> #include <map> #include <vector> #include <cstdlib> #include <cmath> #include <algorithm> #include <queue> #include <set> #include <stack> #include<cstdio> #include<cstring> int ans[1005]; void getans() { ans[1]=1; ans[2]=1; ans[3]=2; ans[4]=3; for(int i=5; i<1001; i++) { for(int j=1; j<i; j++) { if((i-1)%j == 0) { ans[i] += ans[j]; ans[i] %= 1000000007; } } } } int main() { int n,ncase=1; memset(ans,0,sizeof(ans)); getans(); while(scanf("%d",&n)!=EOF) printf("Case %d: %d\n",ncase++,ans[n]); return 0; }
努力努力...