首页 > 代码库 > UVa 1645 (递推) Count
UVa 1645 (递推) Count
题意：
有多少个n个节点的有根树，满足每层节点的子节点个数相同，输出该数目除以1e9+7的余数。
分析：
这种题目就属于那种，看起来很高冷，读完题更高冷。想了N久想不出来，一搜题解，卧槽，这么sb的题我都不会。
言归正传，根据题意，这棵树是关于根节点对称的，对称性非常好，根节点下面的子树也完全相同。
所以就有了如下递推关系：
1 #include <cstdio> 2 #include <cmath> 3 4 const int maxn = 1000; 5 const int MOD = 1000000000 + 7; 6 int ans[maxn + 10]; 7 8 void Init() 9 {10 ans[1] = 1;11 for(int i = 2; i <= maxn; ++i)12 {13 int m = sqrt(i);14 for(int j = 1; j <= m; ++j) if((i-1) % j == 0)15 {16 if(j * j == i - 1) ans[i] = (ans[i] + ans[j]) % MOD;17 else ans[i] = (((ans[i] + ans[j])%MOD) + ans[(i-1)/j]) % MOD;18 }19 }20 }21 22 int main()23 {24 Init();25 int kase = 0, n;26 while(scanf("%d", &n) == 1)27 printf("Case %d: %d\n", ++kase, ans[n]);28 29 return 0;30 }
UVa 1645 (递推) Count
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。